GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

PROBLEM SET

动态规划

按知识点筛选题目，系统巩固该考点。

共 605 题

重置

全部知识点基础数学知识模拟枚举深度优先搜索递推贪心基础排序栈区间动态规划最短路算法队列字符串结构体排序动态规划前缀和拓扑排序线性动态规划树形动态规划递归背包动态规划最近公共祖先二分答案并查集线段树 sort排序基础算法高精度分治素数筛法

题目列表

共 605 题

A66056 C语言等级考试三级真题：放苹果。把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。输出对输入的每组数据M和N，用一行输出相应的K。… 2022年 动态规划递归组合计数整数划分 -- -- A66055 C语言等级考试四级真题：最长上升子序列。一个数字的序列b i，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列( a 1 , a 2 , ..., a N )，我们可以得到一些上升的子序列( a i 1 , a i 2 , ..., a i K )，这里 1 <= i 1 < i 2 < ... < i K … 2022年 动态规划循环结构数组最长上升子序列 -- -- A66054 C语言等级考试四级真题：神奇的口袋。有一个神奇的口袋，现在这个总物品是 40 件，用起来可以变出几件物品，这些物品的总体积是 40 件。，一个2 …… 一个约翰约翰可以从中选择一些神奇的事物，可以从这些物体的总体积中选择 4个，如果是这些事物的神奇的总体积，约翰就可以揭穿约翰就得到了物品。现在约翰有多少种不同的选择物品的方式。输入输入的第一行是正n n <= 2 (0) 个不同的项目。… 2022年 动态规划递归组合计数背包问题 -- -- A66053 C语言等级考试四级真题：滑雪（滑雪目测）。迈克尔坡喜欢发现这并不重要，因为看到坡确实很刺激。为了获得，你必须加快滑行的区域，而当你滑到底部时，你又是再次上等待下台走来装载。迈克尔想知道一个区域中长度的滑动。区域由一个范围内的滑坡提供。这里的每个数字代表点的高度。下面是一个例子1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9… 2022年 深度优先搜索动态规划二维数组记忆化搜索 -- -- A66052 C语言等级考试四级真题：删除数字。娇娇当年级了，刚学会了识数和比大小。昨天，她在黑板上写上一串数字：2，1，2，5，4。接着她擦掉了第一个2，发现剩下的1，2，4都在自己的位置上，即：1在第1位，2在第2位，4在第4位。娇娇希望在自己的上擦掉一些数后能有几个问题，她的数数在自己上的位置上。！ 2022年 动态规划最长递增子序列数组处理 -- -- A66039 青少年C语言等级考试八级真题：道路（roads）。N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后，Bob和她分手了，并且决定搬到城市N。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的… 2022年 动态规划图论最短路径状态约束 -- -- A66020 公共子序列。我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在严格上升的序列< i1, i2, ..., ik >，使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b,… 2022年 字符串动态规划最长公共子序列多组输入 -- -- A66018 上机。又到周末了，同学们陆陆续续开开心心的来到机房上机。jbr也不例外，但是他到的有点晚，发现有些机位上已经有同学正在做题，有些机位还空着。细心的jbr发现，一位同学来到机房，坐在机位i上，如果他的左右两边都空着，他将获得能力值a[i]；如果当他坐下时，左边或者右边已经有一个人在上机了，他将获得能力值b[i]；如果当他坐下时，他的左边右边都有人在上机，他将获得能力值c[i]。同时他发现，已经在上… 2022年 动态规划区间DP 状态转移 -- -- A66017 硬币问题。有N（不大于100）种硬币，编号为1至N，已知每种硬币的重量（不超过100的正整数）和面额（不超过100的正整数），每种硬币数量不限。选取总重量不超过C（不大于1000的正整数）的硬币，最多能获得多少总面额？第二行输入C 第三行输入各硬币重量，用空格隔开第四行输入各硬币价值，用空格隔开输出最大总面额样例输入351 2 51 3… 2022年 动态规划数组完全背包 -- -- A70884 导弹拦截 编程题 贪心动态规划最长不下降子序列入门 -- A58222 编写程序计算n(n<=10)位数中，包含奇数个5的个数。比如1位数中包含奇数个5的个数是1个。利用递推方法计算n位数包含奇数个5的个数。完善划线处的代码。c = [[0 for i in range(2)] for i in range(11)] #存放奇数个5和偶数个5的二维列表 2022年 递推动态规划循环结构 -- -- A63245 蓝桥杯C++国赛编程实现: 数学实验。【 创意编程组 动态规划区间DP 合并操作 -- -- A63244 蓝桥杯C++国赛编程实现: 摆渡车。【 创意编程组 动态规划贪心策略前缀和优化时间序列 -- -- A63242 蓝桥杯青少组Python国赛编程题：有一个由多个小正六边形组成的蜂巢图案，蜂巢外缘各边的小正六边形数量一致，且左右对称。以下为竖直对称线上小正六边形个数为3、5、7的3个蜂巢图案。编程实现：有一只蜗牛要从竖直对称线顶端的小正六边形处移动到底端的小正六边形中，它每次只能向它所在位置的小正六边形的左下方、正下方、右下方相邻的小正六边形处移动。已知竖直对称线上有N个小正六边形，请计算出蜗牛从竖直对称… 创意编程组 递推动态规划图形化编程路径计数 -- -- A63241 小蓝从公司出发，要去拜访N（3≤N≤15）个客户，已知公司到每个客户的路程时间，及N个客户之间的路程时间。请计算出小蓝拜访完所有客户并返回到公司，最少需要多少时间。（道路双向通行，可重复走）例如：N = 3，有3个客户需要拜访，公司到1号、2号、3号客户的路程时间依次为9，7，5，客户1到客户2和客户3的路程时间依次是4，6，客户2到客户3的路程时间是3。从公司出发拜访完3名客户并返回公司最少需… 创意编程组 动态规划位运算最短路径状态压缩 -- -- A63239 有一组正整数数据，现对这组数据按照如下操作：1）从这组数中找出两个相邻且相同的数，删掉其中一个数，剩下的一个数加1（例如：两个相邻的6，变成一个7）；2）重复操作第1步，直到这组数据中没有相邻且相同的数时，操作结束。现给定N（1≤N≤2000）个正整数，表示这一组数，请问按照要求操作结束后，这组数据中最大的数是多少。注意：不同的操作方式得到的最后结果不同，要求最后的结果是所有操作方式中最大的。 … 创意编程组 动态规划贪心策略区间DP 数组操作 -- -- A57626 有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。问第n年的时候，共有多少头母牛?由递推法可推测，当年数小于等于4的时候，第几年就是有几头牛，即a[1]=1；a[2]=2；a[3]=3；a[4]=4。当n大于4的时候，这时候第一年出生的那个小母牛就也可以生出小母牛了，也就是该考虑小母牛是否可以生了，所以n>4的时候，a[n]=？ 2023年-选择题 递推动态规划数列 -- -- A66500 青少年软件编程（C语言）等级考试（四级）编程题：股票买卖。最近越来越多的人都投身股市，阿福也有点心动了。谨记着“股市有风险，入市需谨慎”，阿福决定先来研究一下简化版的股票买卖问题。假设阿福已经准确预测出了某只股票在未来 N 天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。同一天可以进行多次买卖。但是在第一次买入之后，必须要先卖出，然后才可… 2023年 贪心动态规划数组遍历最大子段和 -- -- A66499 青少年软件编程（C语言）等级考试（四级）编程题：带通配符的字符串匹配。通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。例如，1?456 可以匹配 12456、1… 2023年 字符串动态规划递归通配符匹配 -- -- A66497 青少年软件编程（C语言）等级考试四级编程题：怪盗基德的滑翔翼。怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔… 2023年 动态规划数组遍历最长上升子序列多组测试数据 -- --