动态规划0起点基础题目

1、【例 0】斐波那契数列求和( fib.cpp ) 我们已知的斐波那契序列，其中： a0 = 1 a1 = 1an = an-1 + an-2试对数列进行求和，倒序输出前十五项：S15, S14, S13, . S1。(推荐用数组进行存储)Answer:159698660937623214388543320127421【例 1】最大连续子序列的和。( maxsum.cpp )问题描述给定由 N( N=1000 )个整数组成的序列。求出其中最大连续子序列的和。 输入文件文件名： maxsum.in文件第一行为一个整数 N,第二行为N个用空格分开的整数。 输出文件文件名： maxsum.out 文件

2、中只有一个整数，就是最大连续子序列的和。样例输入103 -2 -7 8 9 12 -7 -1 10 -3 样例输出31【例 2】路径总数。( path.cpp )【问题描述】B 点。如下图所示， 某个街区的道路为网格形状。 小华要从最左上角的A 点走到最右下角的若她只能向下或是向右走，那么，一共有多少条不同的路径可以选择？【输入文件】文件名： path.in文件中有两个整数M和N,分别表示水平道路的条数和竖直道路的条数。【输出文件】文件名： path.out文件中只有一个整数，表示从最上角的走到最右下角的不同的路径的条数。【样例输入】4 6【样例输出】【例 3】可行路径。( path.cpp

3、)【问题描述】如下图所示， 某个街区的道路为网格形状， 但由于某些原因， 街区中的一些路口已经不能通 行了。小华要从最左上角的 A 点走到最右下角的 B 点。若她只能向下或是向右走，那么， 一共有多少条不同的路径可以选择？【输入文件】文件名： path.in文件第一行有三个整数 M、N (和P,分别表示水平道路的条数、竖直道路的条数以及不能 通行的路口的个数。之后P行，每行一对整数，分别表示不能通行的路口所在的行数及列数， 已知，这个路口不会在起点和终点。【输出文件】文件名： path.out 文件中只有一个整数，表示从最上角的走到最右下角的不同的路径的条数。【样例输入】4 7 31 32 7

4、3 4【样例输出】例 4】数字正方形( message.cpp ) 问题描述有一个数字正方形，如：3 9 96 1 82 3 3 每走到一个格子都会有一个得分， 现从左上到右下， 每次只能向右或向下走一个格， 如上图最好的路径是右t右t下t下，可得32分，现试求最大得分输入文件第一行表示正方形边长 n接下来 n 行，每行 n 个数 表示每个格子的得分输出文件输出一个数，最大总得分样例输入33 9 96 1 82 3 3样例输出【例 5.0】接苹果问题描述现在有 n 棵一字排开的苹果树， 每个时刻有且仅有一棵树会掉苹果下来。 你可以开始选 中一颗苹果树站在树下， 每个时刻前你可以选择停留在原地或

5、者移动到任意一棵树下 （移动 后仍然可以接到该时刻的苹果） 。如果掉苹果的时刻你正在掉苹果的树下， 那么掉下的苹果 就是你的啦，可是你能移动的次数有限，所以你想知道最多能接到多少个苹果？【例 5.1】接苹果问题描述现在有 n 棵一字排开的苹果树， 每个时刻有且仅有一棵树会掉苹果下来。 你可以开始选 中一颗苹果树站在树下， 每个时刻前你可以选择停留在原地或者移动到旁边一棵树下 （移动 后可以接到该时刻的苹果） 。如果掉苹果的时刻你正在掉苹果的树下， 那么掉下的苹果就是 你的啦，可是你能移动的次数有限，所以你想知道最多能接到多少个苹果？【例 5.2】移动接苹果问题描述现在有 n 棵一字排开的苹果树

6、， 每个时刻有且仅有一棵树会掉苹果下来。 你可以开始选 中一颗苹果树站在树下， 每个时刻前你可以选择停留在原地或者花费该时间移动到旁边一棵 树下（移动后不能接到该时刻的苹果）。 如果掉苹果的时刻你正在掉苹果的树下， 那么掉下 的苹果就是你的啦，可是你能移动的次数有限，所以你想知道最多能接到多少个苹果？例如：苹果树有 2 棵，掉苹果的序列为 2 1 1 2 2 1 1，你能移动的次数为 2次。第 1 个时间，你选择站在 1 树下，第一颗苹果你没有接到。第 2 个时间，你选择不动，那么可以接到第2 颗苹果。第 3 个时间，你选择不动，那么可以接到第3 颗苹果。第 4 个时间，你选择移动到 2 树下

7、。第 5 个时间，你选择不动，那么可以接到第 5 颗苹果。第 6 个时间，你选择移动到 1 树下。第 7 个时间，你选择不动，那么可以接到第 7 颗苹果。 所以你在只移动两次的前提下，可以最多接到4 颗苹果输入文件第一行有三个整数 A、B C,分别表示时间的长度、树的棵树、最多的移动次数 接下来一行A个数字，每个数字都在 1到n之间，表示掉苹果的树。1=A=100、 1=B=100， 0=C=30。输出文件一个数字表示最多能接到多少个苹果样例输入7 2 22 1 1 2 2 1 1样例输出【例 5.3】环路接苹果( apple.cpp )问题描述现在有 n 棵种在环形道路上的苹果树， 1 号树

8、与第 n 号树相邻， 每个时候有且仅有一棵 树会掉苹果下来。 你可以开始选中一颗苹果树站在树下， 每个时刻前你可以选择停留在原地 或者花费该时间移动到旁边一棵树下 (移动后不能接到该时刻的苹果) 。如果掉苹果的时刻 你正在掉苹果的树下， 那么掉下的苹果就是你的啦， 可是你能移动的次数有限， 所以你想知 道最多能接到多少个苹果？例如：苹果树有 2 棵，掉苹果的序列为 2 1 1 2 2 1 1，你能移动的次数为 2次。第 1 个时间，你选择站在 1 树下，第一颗苹果你没有接到。第 2 个时间，你选择不动，那么可以接到第2 颗苹果。第 3 个时间，你选择不动，那么可以接到第3 颗苹果。第 4 个时

9、间，你选择移动到 2 树下。第 5 个时间，你选择不动，那么可以接到第5 颗苹果。第 6 个时间，你选择移动到 1 树下。第 7 个时间，你选择不动，那么可以接到第7 颗苹果。所以你在只移动两次的前提下，可以最多接到 4 颗苹果 输入文件第一行有三个整数 A、B C,分别表示时间的长度、树的棵树、最多的移动次数 接下来一行 A 个数字，每个数字都在 1 到 n 之间，表示掉苹果的树。 1=A=100、 1=B=100， 0=C=30。输出文件一个数字表示最多能接到多少个苹果样例输入7 2 2 2 1 1 2 2 1 1 样例输出【例 6】最长不降子序列的长度。( MaxLen.cpp )问题描

10、述给定一个由 N 个整数组成的整数序列。求出其中最长不降子序列的长度。 输入文件文件名： MaxLen.in文件第一行为一个整数 N,表示整数序列的长度。第二行为N个用空格分开的整数。输出文件文件名： MaxLen.out 文件中只有一个整数，表示这个序列中最长不降子序列的长度。样例输入103 9 8 12 7 9 1 11 10 7样例输出4例 7】混合水果( fruit.cpp ) 问题描述小明很喜欢喝果汁，尤其是把他们混到一起喝，他觉得这样美味极了！这一天他想着， 是不是能把两个水果单词也混合到一起呢？假设有两个水果单词， A 和B,他要求合并到一个单词C中，满足A是C的子串，并且 B也

11、是C的子串例如 A= apple ” , B= peach” ,那么他们可以混合出 C= peach apple ” , D=appleach ” 小明想知道混合出的水果单词长度最小是多少？输入文件两行每行一个单词，长度小于 100输出文件一个数字表示最小混合水果单词长度样例输入applepeach样例输出8【例 8】最长公共子序列( lcs.cpp)问题描述一个字符串A的子串被定义成从 A中顺次选出若干个字符构成的串。如A= “cdaad，顺次选1，3，5个字符就构成子串cad,现给定两个字符串，求它们的最长共公子串。输入文件第一行两个字符串用空格隔开输出文件最长子串的长度样例输入Abccd

12、 Aecd样例输出【例 9】砝码组合。( weight.cpp )问题描述设有 N 种面值互不相同的砝码，每种砝码的数量已知。若知道所有砝码的总重量不超过 10000，请编写程序计算一下，利用这些砝码共可以称出多少种不同的重量。 输入文件文件名： weight.in文件第一行为整数 N ，表示砝码的种数。第二行为 N 个整数，彼此间互不相同，表示每种砝码的重量。第三行也为 N 个整数，依次表示每种砝码的数量。 输出文件文件名： weight.out 文件中只有一个整数，表示利用这些砝码，能称出的不同重量的数量。样例输入61 2 3 5 10 201 1 1 1 1 2样例输出25【例 10】资

13、源分配。( source.cpp )问题描述设有 M 万元资金用于 N 个工厂的扩建。已经每个工厂的利润增长额同投资的大小有关，工厂i在投资j万元的利润增长额为di,j。请输出对这N个工厂的最优投资方案，使总利润增长额最大。输入文件文件名： source.in文件第一行为两个整数 M、N，分别表示总资金数和工场数。之后 N 行，每行 M+1 个整数，表示对某个工厂投资0、 1、 2, M 万元时的利润增长额。输出文件文件名： source.out文件中只有一个整数，表示最大总利润增长额。样例输入6 40 20 42 60 75 85 900 25 45 57 65 70 730 18 39 6

14、1 78 90 950 28 47 65 74 80 85例11 】开心的金明（happy.pas/c/cpp）【问题描述】金明今天很开心， 家里购置的新房就要领钥匙了， 新房里有一间他自己专用的很宽敞的 房间。更让他高兴的是，妈妈昨天对他说： “你的房间需要购买哪些物品，怎么布置，你说 了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了， 肯定会超过妈妈限定的 N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第 5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不 超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了 k件物品，编号依次为j1 ,j2，”， jk ，则所求的总和为：vj1*wj1+vj2*wj2+, +vjk*wjk 。（其中 * 为乘号）请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件happy.in 的第1行，为两个正整数，用一个空格隔开：N m（其中N （ 30000）表示总钱数，m （ 2