动态规划0起点基础题目

【例0】斐波那契数列求和（fib.cpp）
我们已知的斐波那契序列，其中：
a0 = 1
a1 = 1
a n = a n-1 + a n-2
试对数列进行求和，倒序输出前十五项：S15, S14, S13, (1)
（推荐用数组进行存储）
【例1】最大连续子序列的和。

（maxsum.cpp）
〖问题描述〗
给定由N（N<=1000 ）个整数组成的序列。

求出其中最大连续子序列的和。

〖输入文件〗
文件名：maxsum.in
文件第一行为一个整数N，第二行为N个用空格分开的整数。

〖输出文件〗
文件名：maxsum.out
文件中只有一个整数，就是最大连续子序列的和。

〖样例输入〗
10
3 -2 -7 8 9 12 -7 -1 10 -3
〖样例输出〗
31
【问题描述】
如下图所示，某个街区的道路为网格形状。

小华要从最左上角的A点走到最右下角的B点。

若她只能向下或是向右走，那么，一共有多少条不同的路径可以选择？
【输入文件】
文件名：path.in
文件中有两个整数M和N，分别表示水平道路的条数和竖直道路的
条数。

【输出文件】
文件名：path.out
文件中只有一个整数，表示从最上角的走到最右下角的不同的路径的条数。

【样例输入】
4 6
【样例输出】
56
【问题描述】
如下图所示，某个街区的道路为网格形状，但由于某些原因，街区中的一些路口已经不能通行了。

小华要从最左上角的A点走到最右下角的B点。

若她只能向下或是向右走，那么，一共有多少条不同的
路径可以选择？
【输入文件】
文件名：path.in
文件第一行有三个整数M、N（和P，分别表示水平道路的条数、竖直道路的条数以及不能通行的路口的个数。

之后P行，每行一对整数，分别表示不能通行的路口所在的行数及列数，已知，这个路口不会在起点和终点。

【输出文件】
文件名：path.out
文件中只有一个整数，表示从最上角的走到最右下角的不同的路径的条数。

【样例输入】
4 7 3
1 3
2 7
3 4
【样例输出】
19
【例4】数字正方形（message.cpp）
〖问题描述〗
有一个数字正方形，如：
3 9 9
6 1 8
2 3 3
每走到一个格子都会有一个得分，现从左上到右下，每次只能向右或向下走一个格，如上图最好的路径是右→右→下→下，可得32分，现试求最大得分
〖输入文件〗
第一行表示正方形边长n
接下来n行，每行n个数
表示每个格子的得分
〖输出文件〗
输出一个数，最大总得分
〖样例输入〗
3
3 9 9
6 1 8
2 3 3
〖样例输出〗
32
【例5.0】接苹果
〖问题描述〗
现在有n棵一字排开的苹果树，每个时刻有且仅有一棵树会掉苹果下来。

你可以开始选中一颗苹果树站在树下，每个时刻前你可以选择停留在原地或者移动到任意一棵树下（移动后仍然可以接到该时刻的苹果）。

如果掉苹果的时刻你正在掉苹果的树下，那么掉下的苹果就是你的啦，可是你能移动的次数有限，所以你想知道最多能接到多少个苹果？
【例5.1】接苹果
〖问题描述〗
现在有n棵一字排开的苹果树，每个时刻有且仅有一棵树会掉苹果下来。

你可以开始选中一颗苹果树站在树下，每个时刻前你可以选择停留在原地或者移动到旁边一棵树下（移动后可以接到该时刻的苹果）。

如果掉苹果的时刻你正在掉苹果的树下，那么掉下的苹果就是你的啦，可是你能移动的次数有限，所以你想知道最多能接到多少个苹果？
【例5.2】移动接苹果
〖问题描述〗
现在有n棵一字排开的苹果树，每个时刻有且仅有一棵树会掉苹果下来。

你可以开始选中一颗苹果树站在树下，每个时刻前你可以选择停留在原地或者花费该时间移动到旁边一棵树下（移动后不能接到该时刻的苹果）。

如果掉苹果的时刻你正在掉苹果的树下，那么掉下的苹果就是你的啦，可是你能移动的次数有限，所以你想知道最多能接到多少个苹果？
例如：苹果树有2棵，掉苹果的序列为2 1 1 2 2 1 1，你能移动的次数为2次。

第1个时间，你选择站在1树下，第一颗苹果你没有接到。

第2个时间，你选择不动，那么可以接到第2颗苹果。

第3个时间，你选择不动，那么可以接到第3颗苹果。

第4个时间，你选择移动到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
〖样例输出〗
4
【例5.3】环路接苹果（apple.cpp）
〖问题描述〗
现在有n棵种在环形道路上的苹果树，1号树与第n号树相邻，每个时候有且仅有一棵树会掉苹果下来。

你可以开始选中一颗苹果树站在树下，每个时刻前你可以选择停留在原地或者花费该时间移动到旁边一棵树下（移动后不能接到该时刻的苹果）。

如果掉苹果的时刻你正在掉苹果的树下，那么掉下的苹果就是你的啦，可是你能移动的次数有限，所以你想知道最多能接到多少个苹果？
例如：苹果树有2棵，掉苹果的序列为2 1 1 2 2 1 1，你能移动的次数为2次。

第1个时间，你选择站在1树下，第一颗苹果你没有接到。

第2个时间，你选择不动，那么可以接到第2颗苹果。

第3个时间，你选择不动，那么可以接到第3颗苹果。

第4个时间，你选择移动到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
〖样例输出〗
4
【例6】最长不降子序列的长度。

（MaxLen.cpp）
〖问题描述〗
给定一个由N个整数组成的整数序列。

求出其中最长不降子序列的长度。

〖输入文件〗
文件名：MaxLen.in
文件第一行为一个整数N，表示整数序列的长度。

第二行为N个用空格分开的整数。

〖输出文件〗
文件名：MaxLen.out
文件中只有一个整数，表示这个序列中最长不降子序列的长度。

〖样例输入〗
10
3 9 8 12 7 9 1 11 10 7
〖样例输出〗
4
【例7】混合水果（fruit.cpp）
〖问题描述〗
小明很喜欢喝果汁，尤其是把他们混到一起喝，他觉得这样美味极了！！！
这一天他想着，是不是能把两个水果单词也混合到一起呢？假设有两个水果单词，A和B，他要求合并到一个单词C中，满足A是C的子串，并且B也是C的子串例如A=“apple”，B=“peach”，那么他们可以混合出C=“peachapple”，D=“appleach”
小明想知道混合出的水果单词长度最小是多少？
〖输入文件〗
两行每行一个单词，长度小于100
〖输出文件〗
一个数字表示最小混合水果单词长度
〖样例输入〗
apple
peach
〖样例输出〗
8
【例8】最长公共子序列（lcs.cpp）
〖问题描述〗
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。

如A=“cdaad",顺次选1，3，5个字符就构成子串"cad",现给定两个字符串，求它们的最长共公子串。

〖输入文件〗
第一行两个字符串用空格隔开
〖输出文件〗
最长子串的长度
〖样例输入〗
Abccd Aecd
〖样例输出〗
3
【例9】砝码组合。

（weight.cpp）
〖问题描述〗
设有N 种面值互不相同的砝码，每种砝码的数量已知。

若知道所有砝码的总重
量不超过10000，请编写程序计算一下，利用这些砝码共可以称出多少种不同的重量。

〖输入文件〗
文件名：weight.in
文件第一行为整数N ，表示砝码的种数。

第二行为N 个整数，彼此间互不相同，表示每种砝码的重量。

第三行也为N 个整数，依次表示每种砝码的数量。

〖输出文件〗
文件名：weight.out
文件中只有一个整数，表示利用这些砝码，能称出的不同重量的数量。

〖样例输入〗
6
1 2 3 5 10 20
1 1 1 1 1 2
〖样例输出〗
25
【例10】资源分配。

（source.cpp）
〖问题描述〗
设有M万元资金用于N个工厂的扩建。

已经每个工厂的利润增长额
同投资的大小有关，工厂i在投资j万元的利润增长额为di,j。

请输出对这N
个工厂的最优投资方案，使总利润增长额最大。

〖输入文件〗
文件名：source.in
文件第一行为两个整数M、N，分别表示总资金数和工场数。

之后N行，每行M+1个整数，表示对某个工厂投资0、1、2…M万元时的利润增长额。

〖输出文件〗
文件名：source.out
文件中只有一个整数，表示最大总利润增长额。

〖样例输入〗
6 4
0 20 42 60 75 85 90
0 25 45 57 65 70 73
0 18 39 61 78 90 95
0 28 47 65 74 80 85
【例11】开心的金明
(happy.pas/c/cpp)
【问题描述】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。

于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。

他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。

（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。

【输入文件】
输入文件happy.in 的第1行，为两个正整数，用一个空格隔开：
N m
（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。

）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p
（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）
【输出文件】
输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

【输入样例】
1000 5
800 2
400 5
300 5
400 3
200 2
【输出样例】
3900
*NOIP2006年普及组复赛题。