动态规划 POJ-2373 Dividing the Path 题目链接：[ POJ - 2373 ] 题目大意 有一个直线的山脊，喷泉是一个在中间向两边同时喷的，最近喷a，最远b。同时山脊上有牛，每只牛在一个区域里活动，牛活动的区域只能被一个喷泉的水来覆盖。求最少的喷泉使山脊上所有地方都能有水浇灌到 思路 手工实现优先队列的方法 如果一个队列满足以下条件: 开始为空 每在队尾加入一个元素a之前，都从现有队尾往前删除元素 ，一直删到碰到小于a的元素为止，然后再加入a,那么队列就是递增的，当然队头的元素，一定是队列中最小的 题解代码 #include<bits/stdc++.h> using namespace std; const int INFINITE = 1<<30; const int MAXL = 1000010; const int MAXN = 1010; int F[MAXL]; // F[L]就是答案 int cowThere[MAXL]; //cowThere[i]为1表示点i有奶牛 int N,L,A,B; struct Fx { int x; int f; bool operator<(const Fx & a) const { return f > a.f; } Fx(int xx=0,int ff=0):x(xx),f(ff) { } };// 在优先队列里，f值越小的越优先 priority_queue<Fx> qFx; int main(void) { cin >> N >> L; cin >> A >> B; A <<= 1; B <<= 1; //A,B的定义变为覆盖的直径 memset(cowThere,0,sizeof(cowThere)); for( int i = 0;i < N; ++i ) { int s,e; cin >> s >> e; ++cowThere[s+1]; //从s+1起进入一个奶牛区 --cowThere[e]; //从e起退出一个奶牛区 } int inCows = 0; //表示当前点位于多少头奶牛的活动范围之内 for( int i = 0;i <= L ; i ++) { //算出每个点是否有奶牛 F[i] = INFINITE; inCows += cowThere[i]; cowThere[i] = inCows > 0; } for( int i = A;i <= B ; i += 2 ) //初始化队列 if(! cowThere[i] ) { F[i] = 1; if( i <= B + 2 - A ) //在求F[i]的时候，要确保队列里的点x，x <= i - A qFx.push(Fx(i,1)); } for( int i = B + 2 ; i <= L; i += 2 ) { if(!cowThere[i]) { Fx fx; while(!qFx.empty()) { fx = qFx.top(); if( fx.x < i - B ) qFx.pop(); else break; } if (!qFx.empty()) F[i] = fx.f + 1; } if( F[i- A + 2] != INFINITE) { //队列中增加一个+1可达下个点的点 qFx.push(Fx(i- A + 2, F[i- A + 2])); } } if( F[L] == INFINITE ) cout << -1 <<endl; else cout << F[L] << endl; return 0; } // 复杂度:O(nlogn)

动态规划 POJ-1458 Common Subsequence 题目链接：[ POJ - 1458 ] 题目大意 输入两个串s1,s2, 设MaxLen(i, j)表示: s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j)从 0 开始 算) MaxLen(i,j) 就是本题的“状态” 假定 len1 = strlen(s1)，len2 = strlen(s2) 那么题目就是要求 MaxLen(len1, len2) 思路 显然: MaxLen(n,0) = 0 ( n= 0...len1) MaxLen(0,n) = 0 ( n=0...len2) 递推公式: if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0] MaxLen(i,j) = MaxLen(i-1,j-1) + 1; else MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) ); 时间复杂度 $O(m \times n)$ m, n是两个字串长度 题解代码 #include<bits/stdc++.h> using namespace std; const int maxn = 1000 + 10; int dp[maxn][maxn]; char a[maxn], b[maxn]; int main(void) { while (cin >> a >> b) { memset(dp, 0, sizeof(dp)); int len1 = strlen(a); int len2 = strlen(b); for(int i = 0; i < len1; i++) { for(int j = 0; j < len2; j++) { if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); } } cout << dp[len1][len2] << endl; } return 0; }

动态规划 背包 百炼-2755 神奇的口袋 题目链接：[ HDU - 2069 ] 题目大意 背包问题 思路 设V(m,n)表示在n个数字中插入m个加号所能形成 的表达式最小值，那么: if m = 0 V(m,n) = n个数字构成的整数 else if n < m + 1 V(m,n) = ∞ else V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m ... n-1) Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操 作复杂度是 $O(j-i+1)$ ，可以预处理后存起来。 总时间复杂度: $O(mn^2)$ 题解代码 #include<bits/stdc++.h> using namespace std; int dp[50][50]; int a[50]; int main(void) { int n; cin >> n; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) dp[0][i] = 1; dp[0][0] = 1; for (int i = 1; i <= 40; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i][j - 1]; if (i - a[j] >= 0) dp[i][j] += dp[i - a[j]][j - 1]; } } cout << dp[40][n] << endl; return 0; }

动态规划 01背包 POJ-3624 Charm Bracelet 题目链接：[ POJ - 3624 ] 题目大意 0-1背包 思路 用 F[i][j] 表示取前i种物品，使它们总体积不超过j的 最优取法取得的价值总和。要求 F[N][M] 边界: if (w[1] <= j) F[1][j] = d[1]; else F[1][j] = 0; 用 F[i][j] 表示取前i种物品，使它们总体积不超过j的 最优取法取得的价值总和 递推: F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i]) 取或不取第 i种物品，两者选优 ( j-w[i] >= 0 才有第二项) F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i]) 本题如用记忆型递归，需要一个很大的二维数组，会超内存。注意到这个二维数组的下一行的值，只用到了上一行的正上方及左边的值，因此可用滚动数组的思想，只要一行即可。即可以用一维数组，用“人人为我” 递推型动归实现。 题解代码 #include<bits/stdc++.h> using namespace std; const int maxn = 4000; int dp[13000]; int a[maxn], b[maxn]; int main(void) { int n, m; while (~scanf("%d%d", &n, &m)) { memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]); for (int i = 1; i <= n; i++) for (int j = m; j >= a[i]; j--) dp[j] = max(dp[j], dp[j-a[i]] + b[i]); cout << dp[m] << endl; } return 0; }

动态规划 LIS POJ-1088 滑雪 [ POJ - 1088 ] 题目大意 求最长上升子序列的题目，二维数组稍微转化一下 题解代码 #include<bits/stdc++.h> using namespace std; int dp[105][105]; int h[105][105]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, -1, 0, 1}; struct node{ int h; int x, y; }s[10050]; bool cmp(node a, node b) { return a.h < b.h; } int main(void) { int n, m; cin >> n >> m; int r = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &h[i][j]); dp[i][j] = 1; s[r].h = h[i][j]; s[r].x = i; s[r].y = j; r++; } } sort(s, s + r, cmp); int ans = 1; for (int i = 0; i < r; i++) { int lx = s[i].x; int ly = s[i].y; for (int i = 0; i < 4; i++) { int x = lx + dx[i]; int y = ly + dy[i]; if (x>=1 && y>=1 && x<=n && y<=m && h[x][y] > h[lx][ly]) { dp[x][y] = max(dp[x][y], dp[lx][ly] + 1); ans = max(ans, dp[x][y]); } } } cout << ans << endl; return 0; }

动态规划 最长上升子序列LIS 两种角度及优化算法 题目链接：[ OpenJ_Bailian - 2757 ] 一个数的序列 $b_{i}$，当 $b_{1} < b_{2} < ... < b_{S}$ 的时候，我们称这个序列是上升的。对于给定的一个序列( $a_{1}, a_{2}, ..., a_{N}$ )，我们可以得到一些上升的子序列( $a_{i1}, a_{i2}, ..., a_{ik}$)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。 Input 输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。 Output 最长上升子序列的长度。 Sample Input 7 1 7 3 5 9 4 8 Sample Output 4 题解 找子问题 “求以 $a_{k}（k = 1,2,3…N)$ 为终点的最长上升子序列的 一个上升子序列中最右边的那个数，称为该子序列的长度” “终点”。 虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。 找子问题 “求序列的前n个元素的最长上升子序列的长度”是个子问题，但这样分解子问题，不具有“无后效性” 假设 $F(n) = x$, 但可能有多个序列满足$F(n) = x$。 有的序列的最后一个元素比 $a_{n}+1$ 小，则加上 $a_{n}+1$ 就能形成更长上升子序列； 有的序列最后一个元素不比 $a_{n}+1$ 小......以后的事情受如何达到状态n的影响，不符合“无后效性” “求以 $a_{k}(k = 1, 2, 3...N)$为终点的最长上升子序列的长度”一个上升子序列中最右边的那个数，称为该子序列的“终点”。 虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。 确定状态 子问题只和一个变量-- 数字的位置相关。因此序列中数的位置k就是“状态”，而状态k对应的“值”，就 是以ak做为“终点”的最长上升子序列的长度。 状态一共有N个。 找出状态转移方程 maxLen (k)表示以ak做为“终点”的 最长上升子序列的长度那么: 初始状态：maxLen (1) = 1 maxLen (k) = max { maxLen (i):1<=i < k 且 ai < ak且 k≠1 } + 1 若找不到这样的i，则maxLen(k) = 1 maxLen(k)的值，就是在ak左边， “终点”数值小于ak ，且长度最大的那个上升子序列的长度再加1。 因为ak左边任何“终点”小于ak的子序列，加上ak后就能形成一个更长的上升子序列。 方法一 状态i的值 dp[i] 由若干个值已知的状态值 dp[0], dp[1], ..., dp[i-1] 推出。 复杂度 $O(n^2)$ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAX_N = 2000; int a[MAX_N]; int dp[MAX_N]; int main(void) { int n; cin >> n; for (int i = 0; i < n; i++){ scanf("%d", &a[i]); dp[i] = 1; } for (int i = 1; i < n; i++) for (int j = 0; j < i; j++) if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1); cout << *max_element(dp, dp + n) << endl; return 0; } 方法二 状态i的值 dp[i] 在被更新的时候, 依据 dp[i] 去更新和状态i相关的 dp[i+1], ..., dp[n-1] 的值。 复杂度 $O(n^2)$ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAX_N = 2000; int a[MAX_N]; int dp[MAX_N]; int main(void) { int n; cin >> n; for (int i = 0; i < n; i++){ scanf("%d", &a[i]); dp[i] = 1; } for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if(a[j] > a[i]) dp[j] = max(dp[j], dp[i] + 1); cout << *max_element(dp, dp + n) << endl; return 0; } 优化 将全部 dp[i] 的值初始化为INF。然后数组中除了INF之外为单调递增，所以每个 dp[i] 最多只需要一次更新。对于更新位置不必逐个遍历，可以利用二分搜索，这样复杂度可降为 $O(nlogn)$ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAX_N = 2000; const int INF = 9999999; int a[MAX_N]; int dp[MAX_N]; int main(void) { int n; cin >> n; for (int i = 0; i < n; i++) scanf("%d", &a[i]); fill(dp, dp + n, INF); for (int i = 0; i < n; i++) *lower_bound(dp, dp + n, a[i]) = a[i]; cout << lower_bound(dp, dp + n, INF) - dp << endl; return 0; }

动态规划 最长公共子序列 HDU-1159 Common Subsequence 题目链接：[ HDU - 1159 ] A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y. The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0 题解 输入两个串$s,t$, 设$dp(i,j)$表示: $s$的左边$i$个字符形成的子串，与$t$左边的$j$个字符形成的子串的最长公共子序列的长度(i,j从0 开始算) $dp(i,j)$ 就是本题的“状态” 假定$ len1 = strlen(s)$，$len2 = strlen(t）$ 那么题目就是要求 $dp[len1,len2] $ 显然： $dp(n,0) = 0 ( n= 0…len1)$ $dp(0,n) = 0 ( n= 0…len2)$ 递推公式： if ( s[i-1] == t[j-1] ) //s的最左边字符是s1[0] &emsp;dp(i,j) = dp(i-1,j-1) + 1; else &emsp;dp(i,j) = max(dp(i,j-1), dp(i-1,j) ); 时间复杂度$O(m \times n)$， $m,n$是两个字串长度 #include<iostream> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; char s[1005], t[1005]; int dp[1010][1010]; int main(void) { while(~scanf("%s%s" ,s ,t)){ int len1 = strlen(s); int len2 = strlen(t); for (int i = 0; i <= len1; i++) dp[i][0] = 0; for (int i = 0; i <= len2; i++) dp[0][i] = 0; for (int i = 0; i < len1; i++){ for (int j = 0; j < len2; j++){ if(s[i]==t[j]) dp[i + 1][j + 1] = dp[i][j] + 1; else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]); } } cout << dp[len1][len2] << endl; } return 0; }

动态规划 HDU-2069 Coin Change 题目链接：[ HDU - 2069 ] 题目大意 有五种面值的硬币，面值分别为v1, v2, ..., vn, 数量无限。输入一个数，求这个价值所有可能的硬币组合 思路 定义dp[i][j], 表示价格为i时用j枚硬币的方案数量 dp[i][j] = dp[i][j] + dp[1 - type[k]][j - 1] 题解代码 #include<bits/stdc++.h> using namespace std; const int coin = 101; const int money = 251; int dp[money][coin]; int ans[money]; int type[5] = {1, 5, 10, 25, 50}; void solve(void) { dp[0][0] = 1; for (int i = 0; i < 5; i++) for (int j = 1; j < coin; j++) for (int k = type[i]; k < money; k++) dp[k][j] += dp[k - type[i]][j - 1]; } int main(void) { int s; memset(dp, 0, sizeof(dp)); memset(ans, 0, sizeof(ans)); solve(); for (int i = 0; i < money; i++) for (int j = 0; j < coin; j++) ans[i] += dp[i][j]; while (cin >> s) cout << ans[s] << endl; return 0; }

动态规划 入门 POJ-1163 The Triangle 题目链接：[ POJ - 1163 ] 题目大意 用二维数组存放数字三角形。 D(r, j) : 第r行第j个数字(r, j从1开始算) MaxSum(r, j) : 从D(r, j)到底边的各条路径中，最佳路径的数字之和。 问题:求 MaxSum(1, 1) 思路 典型的递归问题。 D(r, j) 出发，下一步只能走 D(r+1,j) 或者 D(r+1, j+1)。故对于N行的三角形: if ( r == N) MaxSum(r,j) = D(r,j) else MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j) 但是！会超时! 如果每算出一个 MaxSum(r,j) 就保存起来，下次用到其值的时候直接取用，则可免去重复计算。 那么可以用 $O(n^2)$ 时间完成计算。因为三角形的数字总 数是 $n(n+1) {\div} 2$ 然后我们将递归转化为递推即可，之后进行空间优化： 没必要用二维maxSum数组存储每一个 MaxSum(r,j) ,只要从底层一行行向上递推， 那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。 题解代码 #include<bits/stdc++.h> using namespace std; const int maxn = 100 + 10; int dp[maxn]; int map[maxn][maxn]; int main(void) { int n; cin >> n; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) scanf("%d", &map[i][j]); for(int i = 1; i <= n; i++) dp[i] = map[n][i]; for(int i = n - 1; i > 0; i--) for(int j = 1; j <= i; j++) dp[j] = max(dp[j], dp[j+1]) + map[i][j]; cout << dp[1] << endl; return 0; }