PROBLEM SET
动态规划
按知识点筛选题目，系统巩固该考点。
题目列表
共 605 题
A59437
有 2*n的一个长方形方格，用一个1*2的骨牌铺满方格，当n=5时，铺法总数为多少？（ ）
2020年
--
--
A61508
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子…
2020年
--
--
A61468
有正实数构成的数字三角形排列形式如图所示。第一行的数为a2,1，a2,2，第n行的数 为an,1，an,2，...，an,n。从a1,1开始，每一行的数ai,j只有两条边可以分别通向下一行的两个 数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1，an,2，...，an,n中某个数的路径，使得 该路径上的数之和最大。令C[i][j]是从a1,1到ai,j的路径上的…
2019年
--
--
A61465
2019年CSP-S1提高组初赛阅读程序题：t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t,那么t也是s的子序列；空串是任何串的子序列。例如:"acd"是“abcde”的子序列，“acd"是“acd”的子序列，但"adc” 不是“abcde”的子序列。s[x..y]表示s[x] ...s[y]共y-x+l个字符构成的字符串，若…
2019年
--
--
A61463
(取石子) Alice和Bob两个人在玩取石子游戏，他们制定了n条取石子的规则，第i条规则为:如果剩 余的石子个数大于等于a[i]且大于等于b[i]，那么她们可以取走b[i]个石子。他们轮流取石子。如果轮到某 个人取石子，而她们无法按照任何规则取走石子，那么他就输了，一开始石子有m个。请问先取石子的 人是否有必胜的方法? 输入第一行有两个正整数，分别为规则个数n(1≤n≤64),以及石子个数m(…
2019年
--
--
A62026
2023年信奥赛CSP-J1普及组初赛阅读程序2：01 #include<iostream>
2023年
--
--
A62023
(编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。试补全动态规划算法：1.#include <iostream>
2023年
--
--
A62016
最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列X={×1,×2,X3,…,xm}和Y={y1,y2,y3,…,yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z1,Z2,Z3,…,zk},使得序列Z既是序列x的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。(注：序列A是序列B的子序列，当且仅当在保持序列B元素顺序的情况…
2023年
--
--
A62011
【打家劫舍】你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 示例 1：输入：nums = [2,…
2023年
--
--
A62004
(第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中， “路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示…
2023年
--
--
A61426
一只小猪要买 N 件物品(N 不超过 1000)。它要买的所有物品在两家商店里都有卖。第 i 件物品在第一家商店的价格是 a[i]，在第二家商店的价格是 b[i]，两个价格都不小于 0 且不超过 10000。如果在第一家商店买的物品的总额不少于 50000，那么在第一家店买的物品都可以打 95 折（价格变为原来的 0.95 倍）。求小猪买齐所有物品所需最少的总额。输入：第一行一个数 N。接下来 …
2018年
--
--
A61388
有正实数构成的数字三角形排列形式如图所示。第一行的数为 a11；第二行的数从左到右依次为 a21, a22；… 第 n 行的数为 an1, an2, …, ann。从 a11 开始，每一行的数 aij 只有两条边可以分别通向 下一行的两个数 a(i+1)j 和 a(i+1)(j+1)。用动态规划算 法找出一条从 a11 向下通到 an1, an2, …, ann 中某个数的路径，使得该路径上的数…
2017年
--
--
A61377
最长路径）给定一个有向无环图，每条边长度为 1，求图中的最长路径长度。（第五空 2 分，其余 3 分） 输入：第一行是结点数 n（不超过 100）和边数 m，接下来 m 行，每行两个整数 a， b，表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到(n-1)。 输出：最长路径长度。 提示：先进行拓扑排序，然后按照拓扑序计算最长路径。#include <iostream>
2017年
--
--
A61376
体验积分值 (point)卡卡西和小朋友们做完了烧脑的数字游戏，决定放松一下，他们来到了万达乐园，乐园中有很多的游玩项目，每玩一个项目就能获取一定的体验积分，不同的项目产生不同的体验积分，假设乐园所有的游乐项目正好排成一排，并且游客们不能游玩任意相邻的两个项目，那么卡卡西如何挑选游玩项目，使得这次万达行他能获得最多的体验积分值呢。输入：输入共两行，第一行是一个正整数 n ，表示万达乐园的游乐项目…
2017年
--
--
A66255
小杨买饮料
2023年
--
--
A58146
小杨买饮料【问题描述】小杨来到了一家商店，打算购买一些饮料。这家商店总共出售N种饮料，编号从0至N-1，其中编号为i的饮料售价ci元，容量li毫升。小杨的需求有如下几点：1. 小杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买 1 瓶；2. 小杨很渴，所以他想要购买总容量不低于L的饮料；3. 小杨勤俭节约，所以在 1 和 2 的前提下，他希望使用尽可能少的费用。方便起见，你只…
2023年-编程题
--
--
A61869
消消乐(game)小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两 个相邻的元素。现在，他有一个长度为 n 且仅由小写字母构成的字符串。我们称一个字符串是可消 除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。 其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。小 L 想知道，这个字符串的所有非空连续子串中，有多少个是…
2023年
--
--
A66236
踩方格有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b. 走过的格子立即塌陷无法再走第二次；c. 只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。 <= 20)输出计算…
2023年
--
--
A68032
酒鬼Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是，瓶子中的酒都有不同的味道。房东说道：“你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，并且不能连续超过三瓶，不然会给你带来坏运气。”现在…
编程题
--
--
A66233
大盗阿福阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
2023年
--
--