最近做了一些动态规划的题目，稍微回顾一下
题意：中文题……
分析：这个题目在黑书上面有，主要是将公式稍微转换一下
hdu2517
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<math.h> using namespace std; const int N = 10; const int M = 20; const int n = 8; double dp[M][N][N][N][N], ss[N][N][N][N]; int a[N][N], s[N][N]; double sum(int x1, int y1, int x2, int y2) { if(ss[x1][y1][x2][y2] >= 0) return ss[x1][y1][x2][y2]; int tmp = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]; return ss[x1][y1][x2][y2] = tmp * tmp; } double DP(int k, int x1, int y1, int x2, int y2) { if(k == 1) { double tmp = sum(x1, y1, x2, y2); return dp[k][x1][y1][x2][y2] = tmp; } double tmp = dp[k][x1][y1][x2][y2]; if(tmp >= 0) return tmp; tmp = 99999999999; for(int i = x1; i < x2; ++i) { tmp = min(tmp , DP(k - 1, x1, y1, i, y2) + sum(i + 1, y1, x2, y2)); tmp = min(tmp , DP(k - 1, i + 1, y1, x2, y2) + sum(x1, y1, i , y2)); } for(int j = y1; j < y2; ++j) { tmp = min(tmp , DP(k - 1, x1, y1, x2, j) + sum(x1, j + 1, x2, y2)); tmp = min(tmp , DP(k - 1, x1, j + 1, x2, y2) + sum( x1 , y1, x2, j)); } return dp[k][x1][y1][x2][y2] = tmp; } int main() { int m; while(scanf("%d",&m) == 1) { memset(s, 0 ,sizeof(s)); int tot = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { scanf("%d",&a[i][j]); tot += a[i][j]; s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j -1 ]; } memset(dp,-1,sizeof(dp)); memset(ss,-1,sizeof(ss)); double ans = DP(m, 1, 1, n, n); double ave = s[n][n] * 1.0 / m; ave *= ave; printf("%.3f\n",sqrt(ans * 1.0 / m - ave)); } return 0; }
此题用dp解决相当灵活，这个博客解释的很不错 http://blog.chinaunix.net/uid-20494489-id-1940446.html
pku1015#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> using namespace std; const int N = 850; int dp[25][N], path[25][N]; int sub[N], plus[N], ans[25]; int main() { int a, b, n, m, cas = 0; while(scanf("%d %d",&n,&m) == 2 && (n || m)) { for(int i = 1; i <= n; ++i) { scanf("%d %d",&a,&b); sub[i] = a - b; plus[i] = a + b; } memset(dp,-1,sizeof(dp)); memset(path,-1,sizeof(path)); int low = 21 * m; dp[0][low] = path[0][low] = 0; for(int i = 1; i <= n; ++i) //先计算选择一个人的情况 { if(dp[1][low + sub[i]] < plus[i]) { path[1][low + sub[i]] = i; dp[1][low + sub[i]] = plus[i]; } } for(int i = 1; i < m; ++i) for(int j = 0; j < 2 * low; ++j) { if(path[i][j] >= 0) { for(int k = 1; k <= n; ++k) { if(dp[i + 1][ j + sub[k] ] < dp[i][j] + plus[k]) { int ii = i, jj = j; for(; ii >= 1; --ii) //判断k是否已经在dp[i][j]中 { if(path[ii][jj] == k) break; jj -= sub[ path[ii][jj] ]; } if( ii < 1 ) { dp[i + 1][ j + sub[k] ] = dp[i][j] + plus[k]; path[i + 1][ j + sub[k] ] = k; } } } } } int tmp; for(int i = 0; i < low; ++i) { if( dp[m][ low + i ] >= 0 || dp[m][ low - i ] >= 0) { if(dp[m][ low + i ] > dp[m][ low - i ]) tmp = low + i; else tmp = low - i; break; } } printf("Jury #%d\n",++cas); printf("Best jury has value %d for prosecution and value %d for defence:\n",(dp[m][tmp] + tmp - low)/2,(dp[m][tmp] - tmp + low)/2); int num = 0; for(int j = m, k = tmp; j >= 1; --j) { ans[num++] = path[j][k]; k -= sub[ ans[num - 1] ]; } sort(ans, ans + num); for(int i = 0; i < num; ++i) printf(" %d",ans[i]); puts(""); } return 0; }
题意：给出m个村庄及其距离，给出n个邮局，要求怎么建n个邮局使代价最小。
分析：
先预处理，把第i个村子到第j个村子中，建一个邮局的最小代价算出来，存在cost[i][j]里。
接下来就可以DP。设dp[i][j]为前i个邮局，建在前j个村子的最小代价。
那么dp[i][j]可以转移到dp[i + 1][j + k]，(1 <= k 且 j + k <= n)，代价是cost[j + 1][j + k]。
pku1160
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> using namespace std; const int N = 300 + 10; int cost[N][N], dp[35][N]; int seq[N]; int main() { int n, m; while(scanf("%d %d",&n,&m) == 2) { for(int i = 1; i <= n; ++i) scanf("%d",&seq[i]); for(int i = 1; i <= n; ++i) { for(int j = i; j <= n; ++j) { cost[i][j] = 0; int mid = (i + j) >> 1; for(int k = i; k <= mid; ++k) cost[i][j] += seq[mid] - seq[k]; for(int k = mid + 1; k <= j; ++k) cost[i][j] += seq[k] - seq[mid]; } } for(int i = 0;i <= m; ++i) for(int j = 0; j <= n; ++j) dp[i][j] = INT_MAX; dp[0][0] = 0; for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) if(dp[i][j] < INT_MAX) { for(int k = 1; j + k <= n; ++k) dp[i + 1][j + k] = min(dp[i + 1][j + k], dp[i][j] + cost[j + 1][j + k]); } printf("%d\n",dp[m][n]); } return 0; }
多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。
随后n-1步按以下方式操作：
(1)选择一条边E以及由E连接着的2个顶点V1和V2；
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题:对于给定的多边形，计算最高得分。
分析：记忆化搜索
dp1[i][j] 表示以i 开始长度为j 的链的最大值，
dp2[i][j] 为最小值
假设当前要求的是dp1[i][j],通过枚举这条长度为J 的直链断开的地方，切成俩段，再迭代求子链
注意存在负值，所以做乘法运算的时候需要用到左右子链的最小值，假设左右自链的最大最小值分别为a， b， c， d， 所以dp1[i][j] = max(a*c, max(a*d, max(b*c, b*d)));
pku1179
#include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; const int N = 50 + 10; int dp1[N][N], dp2[N][N], n; //dp1[i][j] 表示以i 开始长度为j 的链的最大值， //dp2[i][j] 为最小值 int v[N]; char op[N]; void DP(int s, int len) { if(len == 0) { dp1[s][len] = dp2[s][len] = v[s]; return ; } if(dp1[s][len] != INT_MIN) return ; for(int i = s; i < s + len; ++i) { int s1 = i + 1 > n ? (i + 1) - n : i + 1; int len1 = i - s, len2 = len - 1 - (i - s); DP(s, len1); DP(s1, len2); int a = dp1[s][len1], b = dp2[s][len1]; int c = dp1[s1][len2], d = dp2[s1][len2]; int in = i > n? i - n : i ; if(op[in] == '+') { dp1[s][len] = max(dp1[s][len], a + c); dp2[s][len] = min(dp2[s][len], b + d); } else { dp1[s][len] = max(dp1[s][len], max(a * c, max(a * d, max(b * c, b * d)))); dp2[s][len] = min(dp2[s][len], min(a * c, min(a * d, min(b * c, b * d)))); } } return ; } int main() { while(scanf("%d",&n) == 1) { char str[5]; for(int i = 1; i <= n; ++i) { scanf("%s %d",str,&v[i]); op[i] = str[0] == 't' ? '+' : '*'; } int tmp = op[1]; for(int i = 2; i <= n; ++i) op[i - 1] = op[i]; op[n] = tmp; for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) dp1[i][j] = INT_MIN, dp2[i][j] = INT_MAX; int ans = INT_MIN; for(int i = 1; i <= n; ++i) { DP(i, n - 1); ans = max ( ans, dp1[i][n - 1] ); } printf("%d\n",ans); bool flag = true; for(int i = 1; i <= n; ++i) { if( dp1[i][n - 1] == ans ) { if(flag) { printf("%d",i); flag = false; } else printf(" %d",i); } } puts(""); } return 0; }
题意：中文题目……
求拔掉某些钉子后，小球落在编号为m的格子中的概率pm。
那么计算过程中记录某个落到某一个各自的概率，中间涉及到分数的问题。当时，如果注意到一点，所有概率值的分母都是2^k，所以，初始概率dp[0][0] 的值初始化为2n 而不是1，这样就避免了分数的运算，最后再将结果处理一下即可。
pku1189
#include <stdio.h> #include <string.h> long long dp[56][56]; long long gcd(long long x, long long y) { if( y == 0 ) return x; return gcd(y, x % y); } int main() { int n, m; char s[2]; while(scanf("%d %d",&n,&m) == 2) { memset(dp,0,sizeof(dp)); dp[1][1] = (long long)1 << 56; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= i; ++j) { scanf("%s",s); if(s[0] == '*') { dp[i + 1][j] += (dp[i][j] >> 1); dp[i + 1][j + 1] += (dp[i][j] >> 1); } else dp[i + 2][j + 1] += dp[i][j]; } } long long r = dp[n + 1][m + 1]; if( r == 0) { printf("0/1\n"); continue; } long long h = gcd(r, dp[1][1]); if( h == 1 ) { printf("%lld\n",r); continue; } printf("%lld/%lld\n",(long long) r/h,dp[1][1]/h); } return 0; }
题意：给定N 个字符串，求能包含这N 个字符串的最短长度序列。
分析：N 最大为10，所以可以使用状态压缩+ spfa
首先预处理一下数组g[i][j]，表示以第j个字符串接在第i个字符串后面的第一个匹配位置。
dp[v][state]表示以第v的字符串结尾，状态为state时的最短长度，state的每一个2进制位为1表示已经包含了某一个字符串
pku1699
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<vector> #include<queue> using namespace std; const int N = 10 + 5; const int M = 20 + 10; char str[N][M]; int g[N][N], len[N]; int n; int dp[N][1 << N]; bool vis[N][1 << N]; struct node { int v,state; node(){} node(int v,int state):v(v),state(state){} }; void spfa() { memset(vis,false,sizeof(vis)); memset(dp,-1,sizeof(dp)); dp[0][0]=0; queue<node> Q; Q.push(node(0,0)); vis[0][0]=true; while(!Q.empty()) { node tmp=Q.front(); Q.pop(); vis[tmp.v][tmp.state]=false; for(int i = 1; i <= n; ++i) { int state = tmp.state | (1 << (i - 1)); if(tmp.v == i || (tmp.state & ( 1 << (i - 1) ))) continue; if(tmp.v == 0) { dp[i][state] = len[i]; Q.push(node(i, state)); vis[i][state] = true; continue; } int u = tmp.v, v = i, L = len[v] - (len[u] - g[u][v]); if(L >= 0 && (dp[v][state] == -1 || dp[v][state] > dp[u][tmp.state] + L)) { dp[v][state] = dp[u][tmp.state] + L; if(!vis[v][state]) { vis[v][state]=true; Q.push(node(v,state)); } } if(L <= 0) { v = u; L = 0; if(dp[v][state] == -1 || dp[v][state] > dp[u][tmp.state] + L) { dp[v][state] = dp[u][tmp.state]; if(!vis[v][state]) { vis[v][state] = true; Q.push(node(v,state)); } } } } } } int match(int a, int b) { int res = 0; for(; res < len[a]; ++res) { int i = res, j = 0; while(i < len[a] && j < len[b]) { if(str[a][i] != str[b][j]) break; ++i; ++j; } if(j == len[b] || i == len[a] ) break; } return res; } void init() { for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if( i == j ) g[i][j] = 0; else g[i][j] = match(i, j); } g[0][i] = len[i]; } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i = 1; i <= n; ++i) { scanf("%s",str[i]); len[i] = strlen(str[i]); } init(); //for(int i = 1; i <= n; ++i) //{ // for(int j = 1; j <= n; ++j) // cout << g[i][j] << ' '; // cout << endl; //} spfa(); int ans = INT_MAX; for(int i = 1; i <= n; ++i) { if(dp[i][(1 << n) - 1] == -1) continue; ans = min(ans, dp[i][(1 << n) - 1]); } printf("%d\n",ans); } return 0; }
题意：有n个骨牌,每个骨牌上有两个数字,可以通过旋转使得上下两个数字调换.求使得上方数字和与下方数字和最小的最少旋转次数
分析：数组dp[i][j]表示到i个骨牌为止上下差值为j时的最小旋转次数，当然，与背包问题类似，只要一个一维数组即可。注意，差值可能为负，所以需要再加上一个数，将其变为正
pku1717
#include<iostream> #include<algorithm> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; const int N = 1000 + 10; const int M = 12020 + 10; int dp[2][M]; int a[N]; int main() { int n, low; int c, d; while(scanf("%d",&n) == 1) { low = 1; for(int i = 0; i < n; ++i) { scanf("%d %d",&c,&d); a[i] = c - d; low += abs(a[i]); } int m = low * 2; for(int i = 0; i <= m; ++i) dp[0][i] = INT_MAX; dp[0][low + a[0]] = 0; dp[0][low - a[0]] = 1; for(int i = 1; i < n; ++i) { for(int j = 0; j <= m; ++j) dp[i & 1][j] = INT_MAX; for(int j = 0; j <= m; ++j) { if(dp[(i - 1) & 1][j] == INT_MAX) continue; dp[i & 1][j + a[i]] = min(dp[i & 1][j + a[i]], dp[(i - 1) & 1][j]); dp[i & 1][j - a[i]] = min(dp[i & 1][j - a[i]], dp[(i - 1) & 1][j] + 1); } } int ans = INT_MAX; for(int i = 0; i <= low; ++i) { if(dp[(n - 1) & 1][low - i] != INT_MAX || dp[(n - 1) & 1][low + i] != INT_MAX) { ans = min(dp[(n - 1) & 1][low - i], dp[(n - 1) & 1][low + i]); //cout << i << endl; break; } } printf("%d\n",ans); } return 0; }
题意：在一个天平上，要求将左右砝码都挂上，使得左右平衡的方法数。
分析：与上面一道题目类似，dp[i][j] 表示挂上前i个砝码，平衡度为j时的方法数
pku1837
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> using namespace std; const int N = 25; int dp[N][10010]; int w[N],c[N]; //dp[i][j] 表示 挂前i 个砝码的平衡度为j ， j == 5000 表示左右平衡， j < 5000 表示左边偏重， j > 5000 表示右边偏重 int main() { int n, m; while(scanf("%d %d",&n,&m) == 2) { for(int i = 1; i <= n; ++i) scanf("%d",&c[i]); for(int i = 1; i <= m; ++i) scanf("%d",&w[i]); memset(dp,0,sizeof(dp)); dp[0][5000] = 1; for(int i = 1; i <= m; ++i) { for(int j = 0; j <= 10000; ++j) { if(dp[i - 1][j] > 0) { for(int k = 1; k <= n; ++k) dp[i][j + w[i] * c[k]] += dp[i - 1][j]; } } } printf("%d\n",dp[m][5000]); } return 0; }
题意：典型的数型结合的题目
周源的论文上有详细的理论解法
pku2018
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> using namespace std; const int N = 100000 + 10; int q[N], sum[N]; inline bool cmp(int s1, int len1, int s2, int len2) { return s1 * 1ll * len2 < s2 * 1ll * len1; } int scan() { char ch; while( ch = getchar(), ch < '0' || ch > '9'); int res = ch - '0'; while( ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - '0'; return res; } int main() { int n, F, t; while(scanf("%d %d",&n,&F) == 2) { q[0] = sum[0] = 0; for(int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + scan(); } int head = 0, tail = 0; for(int i = 1; i < F; ++i) { while(head < tail && cmp(sum[i] - sum[q[tail]], i - q[tail],sum[q[tail]] - sum[q[tail - 1]], q[tail]- q[tail - 1])) --tail; q[++tail] = i; } int ans = sum[F], len = F; for(int i = F; i <= n; ++i) { while(head < tail && i - q[head + 1] >= F && cmp(sum[i] - sum[q[head]], i - q[head], sum[i] - sum[q[head + 1]], i - q[head + 1])) ++head; while(head < tail && cmp(sum[i] - sum[q[tail]], i - q[tail], sum[q[tail]] - sum[q[tail - 1]], q[tail] - q[tail - 1])) --tail; q[++tail] = i; if(i - q[head] >= F && cmp(ans, len, sum[i] - sum[q[head]], i - q[head])) { ans = sum[i] - sum[q[head]]; len = i - q[head]; } } printf("%d\n",1000 * ans / len); } return 0; }
题意：给n组数，每组数中有S，T值，在其中选取若干组使其所有S+T和最大，要求左边S的和非负，且右边T的和非负
分析：背包的灵活运用，用dp[j]数组，下标表示S的值，dp[j] 的值表示S==j时T的最大值
pku2184
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> using namespace std; const int N = 100 + 10; const int M = 200000 + 10; int dp[M]; int s[N], f[N]; int main() { int n; while(scanf("%d",&n) == 1) { int low = 0, high = 0; for(int i = 0; i < n; ++i) { scanf("%d %d",&s[i],&f[i]); if(s[i] < 0) low -= s[i]; else high += s[i]; } int m = low + high; for(int i = 0; i <= m; ++i) dp[i] = INT_MIN; dp[low] = 0; for(int i = 0; i < n; ++i) { if(s[i] < 0){ for(int j = 0; j <= m; ++j) { if(j + s[i] >= 0 && dp[j] != INT_MIN) dp[j + s[i]] = max(dp[j + s[i]], dp[j] + f[i]); } } else { for(int j = m; j >= 0; --j) { if(j + s[i] <= m && dp[j] != INT_MIN) dp[j + s[i]] = max(dp[j + s[i]], dp[j] + f[i]); } } } int ans = -1; for(int i = low; i <= m; ++i) { int tmp = i - low + dp[i]; if(dp[i] >= 0 && tmp> ans) ans = tmp; } printf("%d\n",ans); } return 0; }
题意：一节课有N分钟，ZZ需要睡M分钟，每分钟都有其效益值，ZZ若听课，则必须连续听L分钟以上。问能获得的最大效益值。M分钟的睡眠可以不连续
分析：用数组dp[i][j] 表示前i分钟睡j分钟获得的最大值，当然，只有这样是没办法完成状态的转移的，还需要一个辅助数组v[j]，表示前i分钟到至少i-L分钟不睡获得的最大价值。
所以v[j] = max( v[j] + a[i], dp[i - L][j] + sum[i] - sum[i - L])
hdu3905
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> using namespace std; const int N = 1000 + 10; int dp[N][N], a[N], v[N]; int sum[N]; //dp[i][j]表示前i分钟睡了j分钟的最大价值 //v[j] 表示前i 到至少i-L分钟都清醒是获得的最大价值 int main() { int n, m, L; while(scanf("%d %d %d",&n,&m,&L) == 3) { sum[0] = 0; for(int i = 1; i <= n; ++i) { scanf("%d",&a[i]); sum[i] = a[i] + sum[i - 1]; } dp[0][0] = 0; memset(v,0,sizeof(v)); for(int i = 1; i <= n; ++i) { for(int j = 0; j <= i && j <= m; ++j) { dp[i][j] = dp[i - 1][j - 1];//继续睡觉 if( i - j >= L) { v[j] = max(v[j] + a[i], dp[i - L][j] + sum[i] - sum[i - L]); dp[i][j] = max(dp[i][j], v[j]); } } } printf("%d\n",dp[n][m]); } return 0; }
题意：一直有俩个监狱，分别关着m个犯人，已知r对关系，监狱1中的犯人xi 与 监狱2中的犯人yi 不能呆在同一个监狱。问，在满足以上r对关系的前提下，求最大的k（K <= M/2) ，监狱1有k个人可以和监狱2中的k个人交换
分析：先将必须同时交换的监狱1 和 监狱2 中的犯人分组，记录每组中，分别属于监狱1 和监狱 2 的人数
如case3
8 12 1 1 1 2 1 3 1 4 2 5 3 5 4 5 5 5 6 6 7 6 8 7 8 8
接到的分组情况是这样的：
1 4
4 1
2 1
1 2
得到四组，每组的第一个数字表示属于第一个监狱的人数，第二个数字表示属于第二个监狱的人数。
将这四组进行一个01背包，dp[i][j] 为true表示可以将监狱1中的i个人跟监狱2中的j个人交换
求最大i 满足dp[i][i] 为true即可
pku1636
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<vector> using namespace std; const int N = 400 + 10; pair<int, int> p[N]; vector<int> g[N]; int num, n; bool vis[N]; int dp[N][N]; void dfs(int s) { vis[s] = true; if(s > n) p[num].second++; else p[num].first++; for(int i = 0; i < g[s].size(); ++i) { int v = g[s][i]; if(!vis[v]) dfs(v); } } int main() { int m, a, b; int T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); for(int i = 0; i <= n * 2; ++i) g[i].clear(); for(int i = 0; i < m; ++i) { scanf("%d %d",&a,&b); g[a].push_back(b + n); g[b + n].push_back(a); } memset(vis,false,sizeof(vis)); num = 0; for(int i = 1; i <= 2 * n; ++i) { if(!vis[i]) { p[++num] = make_pair(0,0); dfs(i); } } //for(int i = 1; i <= num; ++i) // cout << p[i].first << ' ' << p[i].second << endl; memset(dp,false,sizeof(dp)); m = n >> 1; dp[0][0] = true; for(int i = 1; i <= num; ++i) { for(int j = m; j >= 0; j--) for(int k = m; k >= 0; --k) if(dp[j][k] && j + p[i].first <= m && k + p[i].second <= m) { int tmp1 = j + p[i].first, tmp2 = k + p[i].second; dp[tmp1][tmp2] = true; } } for(int i = m; i >= 0; --i) { if(dp[i][i]) { printf("%d\n",i); break; } } } return 0; }