2. 动态规划入门_图文

第二部分 动态规划入门

1、数字三角形
有一个由非负整数组成的三角形,第一行只有一个数, 除了最下行之外每个数的左下方和右下方各有一个数。 从第一行的数开始,每次可以往左下或右下走一格, 直到走到最下行,把没沿途经过的数全部加起来。如 何走才能使得这个和尽量大?

2/37

定义函数dis(i, j),含义为:从格子(i, j)出发能得到的最 大和。则原问题的解为:d(1,1)。 用数组a[][]记录每个格子的值,易得递归关系: dis(i, j)=a(i, j) + max{dis(i+1, j), dis(i+1, j+1)} 注意,当i是最大行时,dis(i, j) = a(i, j)。

3/37

dis(i, j)=a(i, j) + max{dis(i+1, j), dis(i+1, j+1)}
#include <bits/stdc++.h> using namespace std; #define N 100 int a[N][N], dis[N][N]; int main() { int i, j, n; scanf("%d", &n); for(i = 0; i < n; i++) for(j = 0; j <= i; j++) scanf("%d", &a[i][j]); for(i = 0; i < n; i++) dis[n-1][i] = a[n-1][i]; for(i = n-2; i >= 0; i--) for(j = 0; j <= i; j++) if(dis[i+1][j] > dis[i+1][j+1]) dis[i][j] = a[i][j] + dis[i+1][j]; else dis[i][j] = a[i][j] + dis[i+1][j+1]; printf("%d\n", dis[0][0]); return 0; }
4/37

2、最长上升子序列
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). 你的任务,就是对于给定的序列,求出最长上升子序 列的长度。
5/37

输入数据 输入的第一行是序列的长度N (1 <= N <= 1000)。第二 行给出序列中的N 个整数,这些整数的取值范围都在 0 到10000。 输出要求 最长上升子序列的长度。 输入样例 7 1735948 输出样例 4
6/37

假定MaxLen (k)表示以ak 做为“终点”的最长上升子 序列的长度,那么: MaxLen (1) = 1 MaxLen (k) = Max { MaxLen (i):1<i < k 且 ai < ak 且 k≠1 } + 1 实际实现的时候,可以不必编写递归函数,因为从 MaxLen(1)就能推算出MaxLen(2),有了MaxLen(1)和 MaxLen(2)就能推算出MaxLen(3)……

7/37

#include <bits/stdc++.h> #define N 1000 int b[N + 10], aMaxLen[N + 10]; int main(void){ int i, j, n; scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", &b[i]); aMaxLen[0] = 1; for(i = 1; i < n; i ++ ) { int nTmp = 0; for(j = 0; j < i; j++) { if(b[i] > b[j]) { if(nTmp < aMaxLen[j]) nTmp = aMaxLen[j]; } } aMaxLen[i] = nTmp + 1; } int nMax = -1; for(i = 0;i < n; i++) if( nMax < aMaxLen[i]) nMax = aMaxLen[i]; printf("%d\n", nMax); return 0; 8/34 }

8/37

3.最长公共子序列
1、问题描述
我们称序列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, c >的子序列。 现在给出两个序列X 和Y,你的任务是找到X 和Y 的 最大公共子序列,也就是说要找到一个最长的序列 Z, 使得Z 既是X 的子序列也是Y 的子序列。 ?输入数据 输入包括多组测试数据。每组数据包括一行,给出两 个长度不超过200 的字符串,表示两个序列。两个字 符串之间由若干个空格隔开。 9/37

? 输出要求 对每组输入数据,输出一行,给出两个序列的最大 公共子序列的长度。 ? 输入样例 abcfbc abfcab programming contest abcd mnp ? 输出样例 4 2 0
10/37

用字符数组 s1 、 s2 存放两个字符串,用 s1[i] 表示 s1 中 的第 i 个字符, s2[j] 表示 s2 中的第 j 个字符(字符编号 从1 开始),用s1i表示s1的前i个字符所构成的子串, s2j 表示 s2 的前 j 个字符构成的子串, MaxLen(i,j) 表示 s1i 和s2j 的最长公共子序列的长度,那么递推关系如 下: if( i ==0 || j == 0 ) MaxLen(i, j) = 0 //两个空串的最长公共子序列长度 是0 else if( s1[i] == s2[j] ) MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1; else MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j));
11/37

#include <bits/stdc++.h> Using namespace std; #define MAX_LEN 1000 char sz1[MAX_LEN]; char sz2[MAX_LEN]; int aMaxLen[MAX_LEN][MAX_LEN]; int main(void) { while( scanf("%s%s", sz1+1 ,sz2+1 ) > 0 ) { int nLength1 = strlen(sz1+1); int nLength2 = strlen(sz2+1); int i, j; for( i = 0; i <= nLength1; i++ ) aMaxLen[i][0] = 0; for( j = 0; j <= nLength2; j++ ) aMaxLen[0][j] = 0;
12/28

12/37

}

} return 0;

for( i = 1; i <= nLength1;i++ ) { for( j = 1; j <= nLength2; j++ ) { if( sz1[i] == sz2[j] ) aMaxLen[i][j] = aMaxLen[i-1][j-1] + 1; else { int nLen1 = aMaxLen[i][j-1]; int nLen2 = aMaxLen[i-1][j]; if( nLen1 > nLen2 ) aMaxLen[i][j] = nLen1; else aMaxLen[i][j] = nLen2; } } } printf("%d\n", aMaxLen[nLength1][nLength2]);

13/37

4.Help Jimmy
1、问题描述
"Help Jimmy" 是在下图所示的场景上完成的游戏:

14/37

场景中包括多个长度和高度各不相同的平台。地面是最低 的平台,高度为零,长度无限。 Jimmy 老鼠在时刻0 从高于所有平台的某处开始下落, 它的下落速度始终为1 米/秒。当Jimmy 落到某个平台上时, 游戏者选择让它向左还是向右跑,它跑动的速度也是1 米/秒。 当Jimmy 跑到平台的边缘时,开始继续下落。Jimmy 每次下 落的高度不能超过MAX 米,不然就会摔死,游戏也会结束。 设计一个程序,计算Jimmy 到地面时可能的最早时间。

15/37

输入数据
第一行是测试数据的组数t(0 <= t <= 20)。每组测试 数据的第一行是四个整数N,X,Y,MAX,用空格分隔。N 是 平台的数目(不包括地面),X 和Y 是Jimmy 开始下落的位 置的横竖坐标,MAX 是一次下落的最大高度。接下来的N 行 每行描述一个平台,包括三个整数,X1[i],X2[i]和H[i]。 H[i]表示平台的高度,X1[i]和X2[i]表示平台左右端点的横 坐标。1<=N<= 1000,-20000 <= X, X1[i], X2[i] <= 20000,0 < H[i] < Y <= 20000(i = 1..N)。所有坐标 的单位都是米。 Jimmy 的大小和平台的厚度均忽略不计。如果Jimmy 恰好 落在某个平台的边缘,被视为落在平台上。所有的平台均不重 叠或相连。测试数据保证Jimmy 一定能安全到达地面。
16/37

输出要求
对输入的每组测试数据,输出一个整数,Jimmy 到地面时可 能的最早时间。

输入样例
1 3 8 17 20 0 10 8 0 10 13 4 14 3

输出样例
23
17/37

分析
Jimmy 跳到一块板上后,可以有两种选择,向左走 或向右走。走到左端和走到右端所需的时间,容易算 出。 如果我们能知道,以左端为起点到达地面的最短时间, 和以右端为起点到达地面的最短时间,那么向左走还 是向右走,就很容易选择了。 将板子从上到下从1 开始进行无重复的编号(高度相 同的板子,哪块编号在前无所谓),那么,和上面两 个子问题相关的变量就只有板子的编号。

18/37

不妨认为Jimmy 开始的位置是一个编号为0,长度为 0 的板子,假设LeftMinTime(k)表示从k 号板子左 端到地面的最短时间,RightMinTime(k)表示从k 号板子右端到地面的最短时间,那么,求板子k 左端 点到地面的最短时间的方法如下:
if ( 板子k 左端正下方没有别的板子) { if( 板子k 的高度 h(k) 大于Max) LeftMinTime(k) = ∞; else LeftMinTime(k) = h(k); } else if( 板子k 左端正下方的板子编号是m ) LeftMinTime(k) = h(k)-h(m) + Min(LeftMinTime(m)+Lx(k)-Lx(m), RightMinTime(m)+Rx(m)-Lx(k));
19/37

#include <bits/stdc++.h> using namespace std; #define MAX_N 1000 #define INF 1000000 int t, n, x, y, maxh; struct Platform { int Lx, Rx, h; } ; Platform aPlatform[MAX_N + 10]; int aLeftMinTime[MAX_N + 10]; int aRightMinTime[MAX_N + 10]; bool MyCompare(const Platform& e1, const Platform& e2) { return e2.h < e1.h; } int MinTime(int L, bool bLeft) { int y = aPlatform[L].h; int i, x; if(bLeft) x = aPlatform[L].Lx; else x = aPlatform[L].Rx;
20/37

}

for(i = L + 1;i <= n;i++) {//找到下一张板子 if(aPlatform[i].Lx<=x && aPlatform[i].Rx>=x) break; } if(i <= n) {//找到了 if(y-aPlatform[i].h > maxh) return INF;//太高 } else {//没找到 if(y > maxh) return INF;//离地面太高 else return y; }//特殊情况处理完毕 int nLeftTime = y-aPlatform[i].h+x-aPlatform[i].Lx; int nRightTime = y-aPlatform[i].h+aPlatform[i].Rx-x; if(aLeftMinTime[i] == -1)//还没有存储值 aLeftMinTime[i] = MinTime(i, true); if(aRightMinTime[i] == -1) aRightMinTime[i] = MinTime(i, false); nLeftTime += aLeftMinTime[i]; nRightTime += aRightMinTime[i]; if(nLeftTime < nRightTime) return nLeftTime; return nRightTime;
21/37

int main(void) { int i, j; scanf("%d", &t); for(i = 0;i < t; i ++) { memset(aLeftMinTime, -1, sizeof(aLeftMinTime)); memset(aRightMinTime, -1, sizeof(aRightMinTime)); scanf("%d%d%d%d", &n, &x, &y, &maxh); aPlatform[0].Lx = x; aPlatform[0].Rx = x;//长度为0的板子 aPlatform[0].h = y; for(j = 1; j <= n; j ++) scanf("%d%d%d", &aPlatform[j].Lx, &aPlatform[j].Rx, &aPlatform[j].h); sort(aPlatform, aPlatform+n+1, MyCompare); printf("%d\n", MinTime(0, true)); } return 0; }
22/37

5、DAG上的动态规划
很多动态规划问题都可以转化为DAG上的最长路、 最短路或路径计数问题。 嵌套矩形问题:有n个矩形,每个矩形可以用两个整 数a、b描述,表示它的长和宽。矩形X(a,b)可以嵌套在 Y(c,d)中,当且仅当a<c,b<d,或者b<c,a<d(相当于把 矩形X旋转90o)。 例如,(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)内。 你的任务是选出尽量多的矩形排成一行,使得除了 最后一个之外,每一个矩形都可以嵌套在下一个矩形 内。如果有多解,矩形编号的字典序应尽量小。 该问题实际上是求DAG上的最长路。
23/37

硬币问题:有n种硬币,面值分别为V1,V2,…,Vn,每 种都有无限多。给定非负整数S,可以选用多少个硬币, 使得面值之和恰好为S?输出硬币数目的最小值和最大 值。1<=n<=100,0<=S<=10000,1<=Vi<=S。 分析:把还需要凑足的钱数作为状态,则问题的初 始状态为S,结束状态为0。当在状态i时,每使用用一 个编号为j的硬币,则状态转移到i – Vj。 结论:该问题是求DAG图的最短路和最长路。

24/37

DAG上的最长路且其字典序最小(嵌套矩形问题)
输入样例 输出样例 10 18 12 16 4 1->2->5->8->10 12 12 14 13 4 1->2->3->5->7
14 25 26 35 36 37 46 47 58 59 68 69 78 79 8 10 9 10 13 1 12 23 35 37 38 45 57 68 9 10 9 11 9 12 10 12 11 6

25/37

用dist(i)表示从结点i出发的最长路长度,则
dist( = i ) max{dist( j ) + 1 | ( i , j ) ∈ E }
int dp(int u) { if(dist[u] >= 0) return dist[u]; dist[u] = 0; next[u] = u; for(所有后继结点v) { k = dp(v)+1; if(k > dist[u]) { dist[u] = k; next[u] = v; } } }
26/37

#include <stdio.h> #include <string.h> #define N 1000 int n, m, dist[N], next[N], graph[N][N]; int dp(int u); int main() { while(scanf("%d%d", &n, &m) == 2) { int i, u, v; memset(graph, 0, sizeof(graph)); memset(dist, -1 ,sizeof(dist));//为什么用-1,用0? for(i = 0; i < m; i++) { scanf("%d%d", &u, &v); graph[u-1][v-1] = 1; } for(i = 0; i < n; i++) if(dist[i] < 0) dp(i); u = dist[0]; v = 0; for(i = 1; i < n; i++)//从小到大保证字典序最小 { if(dist[i] > u)//不能是>=,保证字典序最小 { v = i; u = dist[i]; } } printf("%d ", u); i = 0;

27/37

} int dp(int u) { int v, k; if(dist[u] >= 0) return dist[u]; //终点 dist[u] = 0; next[u] = u; for(v = 0; v < n; v++)//从小到大保证字典序最小 { if(graph[u][v] == 1) { k = dp(v)+1; if(k > dist[u])//不能是>=,保证字典序最小 { next[u] = v; dist[u] = k; } } } return dist[u]; }

} return 0;

i = 0; do { u = v; v = next[v]; if(i++ > 0) printf("->%d", u+1); else printf("%d",u+1); }while(u != v); printf("\n");

28/37

固定终点的最长路和最短路(硬币问题)
输入样例 输出样例
7 187 1 2 5 10 20 50 100 7 187 50 2 5 10 1 100 20 6 187 2 5 10 20 50 100 11111111111111111111111111111111111 11111111111111111111111111111111111 11111111111111111111111111111111111 11111111111111111111111111111111111 11111111111111111111111111111111111 111111111111 6 187 50 2 5 10 100 20 11111111111111111111111111111111111 11111111111111111111111111111111111 11111111111111111111111111111111111 11111111111111111111111111111111111 11111111111111111111111111111111111 111111111111

29/37

输入样例
4 11 1 5 6 7 4 11 6 5 7 1 3 17 3 6 9 3 11 2 5 10

输出样例 2 11 56 11111111111 2 11 65 11111111111 Impossible! 44 2225 2225

30/37

用minC(S)表示数额为S时需要用到的硬币最小数目 用maxC(S)表示数额为S时需要用到的硬币最大数目
?min{minC(S ? V[i ]) + 1},S > 0且?i ,S ≥ V[i ] i ? ? minC(S) = S > 0且?i ,S < V[i ] ? ?1(不可能 ), ? 0, S=0 ? ?

?max{maxC(S ? V[i ]) + 1},S > 0且?i ,S ≥ V[i ] i ? ? maxC(S) = S > 0且?i ,S < V[i ] ? ?1(不可能 ), ? 0, S=0 ? ?
31/37

#include <stdio.h> #include <string.h> #define N1 102 #define N2 10002 #define INF N2 int V[N1], maxC[N2], minC[N2], max_coin[N2], min_coin[N2], n, S; void dp_min(int ss); void dp_max(int ss); void print_ans(int* d, int S); int main() { while(scanf("%d%d", &n, &S) == 2) { int i, j; for(i = 1; i <= n; i++) scanf("%d", &V[i]); minC[0] = maxC[0] = 0; for(i = 1; i <= S; i++) { minC[i] = INF; maxC[i] = -INF; } dp_min(S); dp_max(S); if(minC[S] == INF) printf("Impossible!\n"); else { printf("%d %d\n", minC[S], maxC[S]); print_ans(min_coin, S); print_ans(max_coin, S); } } return 0; }

32/37

void dp_min(int ss) { int i; if(minC[ss] != INF) //已经计算过 return; for(i = 1; i <= n; i++)//开始枚举计算 { if(ss >= V[i])//试探用一个V[i] { if(minC[ss-V[i]] == INF)//没算过 dp_min(ss-V[i]); if((minC[ss-V[i]]!=INF) && (minC[ss]>minC[ss-V[i]]+1)) { minC[ss] = minC[ss-V[i]]+1; min_coin[ss] = V[i]; } } } } void dp_max(int ss) { int i; if(maxC[ss] != -INF) //已经计算过 return;

33/37

} void print_ans(int* d, int S) { while(S > 0) { printf("%d ", d[S]); S -= d[S]; } printf("\n"); }

for(i = 1; i <= n; i++)//开始枚举计算 { if(ss >= V[i])//试探用一个V[i] { if(maxC[ss-V[i]] == -INF)//没算过 dp_max(ss-V[i]); if((maxC[ss-V[i]]!=-INF) && (maxC[ss]<maxC[ss-V[i]]+1)) { maxC[ss] = maxC[ss-V[i]]+1; max_coin[ss] = V[i]; } } }

34/37

#include <stdio.h> #include <string.h> #define N1 102 #define N2 10002 #define INF N2 int V[N1], maxC[N2], minC[N2]; int max_coin[N2], min_coin[N2]; int n, S; void print_ans(int* d, int S); int main() { while(scanf("%d%d", &n, &S) == 2) { int i, j; for(i = 1; i <= n; i++) scanf("%d", &V[i]); minC[0] = maxC[0] = 0; for(i = 1; i <= S; i++) { minC[i] = INF; maxC[i] = -INF; }
35/37

for(i = 1; i <= S; i++) { for(j = 1; j <= n; j++) { if(i >= V[j]) { if((minC[i-V[j]]!=INF) && (minC[i]>minC[i-V[j]]+1)) { minC[i] = minC[i-V[j]]+1; min_coin[i] = V[j]; } if((maxC[i-V[j]]!=-INF) && (maxC[i] < maxC[i-V[j]]+1)) { maxC[i] = maxC[i-V[j]]+1; max_coin[i] = V[j]; } } } }
36/37

} void print_ans(int* d, int S) { while(S > 0) { printf("%d ", d[S]); S -= d[S]; } printf("\n"); }
37/37

} return 0;

if(minC[S] == INF) { printf("Impossible!\n"); } else { printf("%d %d\n", minC[S], maxC[S]); print_ans(min_coin, S); print_ans(max_coin, S); }


相关文档

动态规划入门2
动态规划入门22
动态规划入门(2)
动态规划入门
动态规划入门21
动态规划入门12
动态规划入门13
动态规划基础
动态规划入门19
动态规划入门11
学霸百科
99813842文学网 998138421php网站 998138422jsp网站 998138423小说站 998138424算命网 998138425占卜网 998138426星座网 电脑版 | 学霸百科