等级标准

掌握基本算法中的动态规划方法；能够使用上述方法编写指定功能的正确完整的程序。

1、最长上升子序列

考试题目

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。

时间限制：11000

内存限制：65536

输入

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出

最长上升子序列的长度。

样例输入

7

1 7 3 5 9 4 8

样例输出

4

参考答案

#include <bits/stdc++.h>using namespace std;int main(){#ifdef LOCALfreopen("09_4_1.in", "r", stdin);#endifint N;scanf("%d", &N);int a[1010];for(int i = 0; i < N; i++){scanf("%d", &a[i]);}//定义dp[i]为以i位结尾的最长上升序列长度int dp[1010];memset(dp, 0, sizeof(dp));dp[0] = 1;int max_len = 0;for(int i = 1; i < N; i++){for(int j = i - 1; j >= 0; j--){if(a[i] > a[j]){dp[i] = max(dp[i], dp[j] + 1);}}//printf("%d ", dp[i]);max_len = max(max_len, dp[i]);}printf("%d", max_len);}

2、神奇的口袋

考试题目

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

时间限制：10000

内存限制：65536

输入

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出

输出不同的选择物品的方式的数目。

样例输入

3

20

20

20

样例输出

3

参考答案（递归）

#include<bits/stdc++.h>using namespace std;int goods[30];//从前k种物品中选择一些，凑成体积w的做法数目 int ways(int w, int k){if(w == 0) return 1;//没有需要凑的体积了，刚好凑满 if(k <= 0) return 0;//还差体积或者体积过了，但是没有物品可以选了。 if(w >= goods[k]){return ways(w, k - 1) + ways(w - goods[k], k - 1);//体积:选择第k种物品 + 不选第k种物品}else{return ways(w, k - 1);}}int main(){int n;scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &goods[i]);}printf("%d", ways(40, n)); return 0;}

参考答案(动态规划)

#include<bits/stdc++.h>using namespace std;#define H 40int goods[30];int main(){#ifdef LOCALfreopen("09_4_2.in", "r", stdin);#endifint N;scanf("%d", &N);for(int i = 1; i <= N; i++){scanf("%d", &goods[i]);}int dp[H + 10][30];memset(dp, 0, sizeof(dp));for(int i = 0; i <= N; i++){dp[0][i] = 1;} for(int w = 0; w <= H; w++){for(int k = 1; k <= N; k++){if(w >= goods[k]){dp[w][k] = dp[w][k - 1] + dp[w - goods[k]][k - 1];}else{dp[w][k] = dp[w][k - 1];}}}printf("%d", dp[H][N]); return 0;}

3、滑雪

考试题目

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。

时间限制：1000

内存限制：65536

输入

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

输出

输出最长区域的长度。

样例输入

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

样例输出

25

解题思路

采用递推的动态规划方式求解先用结构体保存每个点对应的原本坐标位置和高度；将所有点按高度从小到大排序；用一个二维数组保存输入的原本数据，再用一个二维数组保存对应位置的最大滑行距离；从第二个点开始求解（因为第一个点高度最低，显然滑行距离为1）依次和它在原本坐标里的上下左右四个方向进行判断，如果它比某一方向上的高度高，则它的滑行距离就应该是相比较的最大滑行距离+1和它保存的最大滑行距离中的最大值。最后求完总共的点，进行遍历，得到最终最大值。

参考答案

#include<bits/stdc++.h>using namespace std;struct point{int r,c,h;}ps[10100];bool cmp(point a,point b){return a.h < b.h; //根据高度从小到大排序，依次求解}int f[110][110]; //保存输入的数组int ans[110][110]; //保存求值的结果int main(){int n,m; //行列 的数cin >> n >> m;//输入数组for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin >> f[i][j];ps[i * m + j].h = f[i][j];ps[i * m + j].r = i;ps[i * m + j].c = j;ans[i][j] = 1; //初始化完成}}sort(ps, ps + n * m, cmp);//开始求解for(int i = 1;i < n * m; i++){int r = ps[i].r;int c = ps[i].c; //得到行列的值//进行四个方向的判断if(r > 0 && ps[i].h > f[r-1][c]) //向上ans[r][c] = max(ans[r][c],ans[r-1][c]+1);if(c > 0 && ps[i].h > f[r][c-1]) //向左ans[r][c] = max(ans[r][c],ans[r][c-1]+1);if(r < n-1 && ps[i].h > f[r+1][c]) //向下ans[r][c] = max(ans[r][c],ans[r+1][c]+1);if(c < m-1 && ps[i].h> f[r][c+1]) //向右ans[r][c] = max(ans[r][c],ans[r][c+1]+1);}//输出结果int maxl = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){maxl = max(maxl, ans[i][j]);}} cout << maxl << endl;return 0;}

4、删除数字

娇娇一年级了，刚刚学会了识数和比大小。有一天，她在黑板上写上了一串数字：2，1，2，5，4。接着她擦掉了第一个2，发现剩下1，2，4都在自己的位置上，即：1在第1位，2在第2位，4在第4位。

娇娇希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个问题很有趣，想知道最多能有几个数在自己的位置上，请你帮帮她！

时间限制：1000

内存限制：65536

输入

第一行，一个整数 TestNum( ≤ 10)，表示测试数据的组数。 接下来每组数据有两行，第一行：一个整数n( ≤ 1000)，第二行：n个正整数(≤ 1000)。

输出

对于每组测试数据，输出一个数表示答案。

样例输入

3

5

2 1 2 5 4

7

2 2 3 2 4 5 3

10

1 1 2 2 3 3 4 4 5 5

样例输出

3

4

5

提示

第一组测试数据：擦掉第一个数，1 2 4 有 3 个数在自己的位置上。

第二组测试数据：擦掉第4个、第7个数，2 3 4 5 有 4 个数在自己的位置上。

第三组测试数据：每种相同的数擦掉一个，1 2 3 4 5 有 5 个数在自己的位置上。

解题思路

d[i][j]表示1到i中删除j个数满足条件的最大个数，

d[i][j]的前一种情况可能是d[i-1][j-1]和d[i-1][j]，若第i个数删除，则为d[i][j]=d[i-1][j-1]，

若第i个数不删，则d[i][j]=d[i-1][j]，

考虑当a[i]==i-j时，若第i个数不删，则符合位置条件的数增加一个，所以比较d[i-1][j-1]和d[i-1][j]+1。

参考答案

#include <bits/stdc++.h>using namespace std;int d[1010][1010]; //全局变量，默认为0，避免数组过大崩溃 //d[i][j]表示1到i中删除j个数满足条件的最大个数 int main(){int i,j,n,a[1010]; int f=0; //初始化标记为0cin>>n;for(i=1;i<=n;i++){cin>>a[i];}for(i=1;i<=n;i++){d[i][0]=d[i-1][0]; //未删除 if(a[i]==i){//统计初始时满足条件个数 d[i][0]++;}}for(i=1;i<=n;i++){for(j=0;j<=i;j++){if(a[i]==i-j){//删除数之后的位置满足条件 d[i][j]=max(d[i-1][j-1],d[i-1][j]+1);}else{//前i个数删除j个，考虑第i个数删和不删的情况 d[i][j]=max(d[i-1][j-1],d[i-1][j]);}}}for(int i=0;i<=n;i++){f=max(f,d[n][i]); //找出最大值 }cout<<f;return 0;}