《挑战程序设计竞赛》课后练习题解集——2.3 记录结果再利用的“动态规划”
2.3 记录结果再利用的“动态规划”
基础的动态规划算法
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
POJ 3176 从三角形顶端走到底边使经过的数字和最大
从下往上逆推答案
1 #include <cmath>
2 #include <iostream>
3 using namespace std; 4
5 int row[355][355]; 6
7 int main() { 8 int n; 9 scanf("%d", &n); 10 for (int i = 1; i <= n; i++) { 11 for (int j = 1; j <= i; j++) scanf("%d", &row[i][j]); 12 } 13 for (int i = n - 1; i >= 1; i--) { 14 for (int j = 1; j <= i; j++) 15 row[i][j] += max(row[i + 1][j], row[i + 1][j + 1]); 16 } 17 printf("%d\n", row[1][1]); 18 }
View Code
POJ 2229 问一个数拆成2的幂次之和有多少种拆法
考虑当前数字的组成方案中可能有几个"1"，把这些1去掉之后，剩下的数（都是偶数）除以二就一一对应于 剩下的数 的和 对应的答案
另解：考虑当前数字的组成方案中是否有1，得出递推关系式 dp[i] = dp[i - 1] + dp[i >> 1]（i为偶数）
1 #include <cstdio>
2 using namespace std; 3
4 const int mod = 1e9; 5 const int maxn = 1e6 + 5; 6
7 int a[maxn], s[maxn], x; 8
9 int main () { 10 a[0] = s[0] = 1; 11 for(int i = 1; i <= 1000000; i++) { 12 a[i] = s[i / 2]; 13 s[i] = (s[i - 1] + a[i]) % mod; 14 } 15 scanf("%d", &x); 16 printf("%d\n", a[x]); 17 }
View Code
POJ 2385 接苹果问题
关键：dp[i][j] 在第i分钟，cow移动了j次
1 #include <cstdio>
2 using namespace std; 3
4 int a[1005], even[1005], n, w; 5 int dp[1005][35]; 6
7 int max(int a, int b) { 8 return a > b ? a : b; 9 } 10
11 int main () { 12 scanf("%d%d", &n, &w); 13 for(int i = 1; i <= n; i++) { 14 scanf("%d", &a[i]); 15 even[i] = even[i - 1] + (a[i] == 1); 16 } 17 for(int i = 1; i<= n; i++) { 18 dp[i][0] = even[i]; 19 for(int j = 1; j <= w; j++) { 20 for(int k = 0; k <= i; k++) { 21 if(j & 1) dp[i][j] = max(dp[k][j - 1] + (i - k) - (even[i] - even[k]), dp[i][j]); 22 else dp[i][j] = max(dp[k][j - 1] + even[i] - even[k], dp[i][j]); 23 } 24 } 25 } 26 printf("%d\n", dp[n][w]); 27 }
View Code
1 #include <cstdio>
2 using namespace std; 3
4 int a[1005], n, w, ans; 5 int dp[1005][35]; 6
7 int max(int a, int b) { 8 return a > b ? a : b; 9 } 10
11 int main () { 12 scanf("%d%d", &n, &w); 13 for(int i = 1; i <= n; i++) { 14 scanf("%d", &a[i]); 15 } 16 for(int i = 1; i <= n; i++) { 17 dp[i][0] = dp[i - 1][0]; 18 for(int j = 1; j <= w; j++) { 19 dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]); 20 } 21 if (a[i] & 1) for(int j = 0; j <= w; j+=2) dp[i][j]++; 22 else for(int j = 1; j <= w; j+=2) dp[i][j]++; 23 } 24 for(int i = 0; i <= w; i++) ans = max(ans, dp[n][i]); 25 printf("%d\n", ans); 26 }
View Code
POJ 3616 给出N个区间及其权值，取不重复的若干区间使权值和最大
（这一题结束时刻是可以与起始时刻重合的）
考虑从时间上的转移或者从具体某一区间转移过来
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std; 5 #define ll long long
6
7 const int maxn = 1e6 + 5; 8
9 int n, m, r; 10 ll dp[maxn]; 11 struct pii { 12 int s, e, val; 13 bool operator < (const pii &o) const { return e < o.e; } 14 } p[maxn]; 15
16 ll max(ll a, ll b) { 17 return a > b ? a : b; 18 } 19
20 int main () { 21 scanf("%d %d %d", &n, &m, &r); 22 for(int i = 0; i < m; i++) { 23 scanf("%d %d %d", &p[i].s, &p[i].e, &p[i].val); 24 p[i].e += r; 25 } 26 sort(p ,p + n); 27 for(int i = 0, t = 0; t <= n + r; t++) { 28 dp[t] = dp[t - 1]; 29 while(i < n && p[i].e == t) { 30 dp[t] = max(dp[p[i].s] + p[i].val, dp[t]); 31 i++; 32 } 33 } 34 printf("%lld\n", dp[n + r]); 35 }
View Code
1 #include <algorithm>
2 #include <cmath>
3 #include <iostream>
4 #include <cstdio>
5 using namespace std; 6 #define ll long long
7
8 ll dp[1005]; 9
10 struct inf { 11 int s, e, v; 12 } inter[1001]; 13
14 bool cmp(const inf &x, const inf &y) { return x.e < y.e; } 15
16 ll max(ll a, ll b) { 17 return a > b ? a : b; 18 } 19
20 int main() { 21 int n, m, r; 22 scanf("%d %d %d", &n, &m, &r); 23 for (int i = 0; i < m; i++) { 24 scanf("%d %d %d", &inter[i].s, &inter[i].e, &inter[i].v); 25 inter[i].e += r; 26 } 27 sort(inter, inter + m, cmp); 28 dp[0] = inter[0].v; 29 for (int i = 1; i < m; i++) { 30 inf t = {0, inter[i].s, 0}; 31 inf *ite = upper_bound(inter, inter + i, t, cmp); 32 if (ite == inter) 33 dp[i] = max(dp[i - 1], (ll)inter[i].v); 34 else
35 dp[i] = max(dp[i - 1], dp[ite - inter - 1] + inter[i].v); 36 } 37 printf("%lld\n", dp[m - 1]); 38 }
View Code
POJ 3280 给出删除和添加某字符的代价，对于给定字符串，求经过操作后的字符串是回文串最小代价
添加和删除是对称的操作，取其中的较小值即可。dp[i][j]代表从位置i到j的字串变成回文串需要的最小代价
1 #include <algorithm>
2 #include <cmath>
3 #include <iostream>
4 using namespace std; 5
6 int value[30], dp[2005][2005]; 7 int n, m, x, y; 8 string str; 9 char s; 10
11 int main() { 12 ios::sync_with_stdio(false); 13 cin >> n >> m >> str; 14 for (int i = 0; i < n; i++) { 15 cin >> s >> x >> y; 16 value[s - 'a'] = min(x, y); 17 } 18 for (int i = m - 1; i >= 0; i--) { 19 for (int j = i + 1; j < m; j++) { 20 if (str[i] == str[j]) { 21 dp[i][j] = dp[i + 1][j - 1]; 22 } else { 23 dp[i][j] = min(dp[i + 1][j] + value[str[i] - 'a'], 24 dp[i][j - 1] + value[str[j] - 'a']); 25 } 26 } 27 } 28 cout << dp[0][m - 1]; 29 }
View Code
优化递推关系式
POJ 1742 多重部分和问题
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 using namespace std; 5
6 int dp[100005], res; 7
8 int a[105], c[105], n, m; 9
10 int main() { 11 while (scanf("%d %d", &n, &m) && n) { 12 memset(dp, -1, sizeof(dp)); 13 dp[0] = res = 0; 14 for (int i = 0; i < n; i++) scanf("%d", &a[i]); 15 for (int i = 0; i < n; i++) scanf("%d", &c[i]); 16 for (int i = 0; i < n; i++) { 17 for (int j = 0; j < a[i]; j++) 18 if (dp[j] >= 0) dp[j] = c[i]; 19 for (int j = a[i]; j <= m; j++) { 20 if (dp[j] == -1) { 21 if (dp[j - a[i]] <= 0) 22 dp[j] = -1; 23 else
24 dp[j] = dp[j - a[i]] - 1; 25 } else { 26 dp[j] = c[i]; 27 } 28 } 29 } 30 for (int i = 1; i <= m; i++) res += (dp[i] >= 0); 31 printf("%d\n", res); 32 } 33 }
View Code
POJ 3046 多重集组合数
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 using namespace std; 5
6 const int mod = 1e6; 7 int res, dp[2][100005]; 8 int t, a, s, b, x; 9 int c[1005]; 10
11 int main() { 12 scanf("%d%d%d%d", &t, &a, &s, &b); 13 for (int i = 0; i < a; i++) { 14 scanf("%d", &x); 15 c[x]++; 16 } 17 dp[0][0] = dp[1][0] = 1; 18 for (int i = 1; i <= t; i++) { 19 for (int j = 1; j <= c[i]; j++) 20 dp[i & 1][j] = (dp[i & 1][j - 1] + dp[1 - i & 1][j]) % mod; 21 for (int j = c[i] + 1; j <= b; j++) 22 dp[i & 1][j] = (dp[i & 1][j - 1] + dp[1 - i & 1][j] -
23 dp[1 - i & 1][j - c[i] - 1] + mod) %
24 mod; 25 } 26 for (int i = s; i <= b; i++) res = (res + dp[t & 1][i]) % mod; 27 printf("%d\n", res); 28 }
View Code
POJ 3181 无数量限制的多重部分和+高精度
dp[i]不再表示当前物品用剩多少，而是方案数
1 #include <algorithm> 2 #include <cstring> 3 #include <iostream> 4 #define ll long long 5 using namespace std; 6 7 string dp[2][1005]; 8 9 string add(string a, string b) { 10 if (a.size() < b.size()) swap(a, b); 11 int f = 0; 12 for (int i = a.size() - 1, j = b.size() - 1; j >= 0; i--, j--) { 13 a[i] += b[j] - '0' + f; 14 if (a[i] > '9') { 15 a[i] -= 10; 16 f = 1; 17 } else 18 f = 0; 19 } 20 for (int i = a.size() - b.size() - 1; i >= 0 && f; i--) { 21 f = 0; 22 a[i]++; 23 if (a[i] > '9') { 24 a[i] -= 10; 25 f = 1; 26 } 27 } 28 if (f) a = "1" + a; 29 return a; 30 } 31 32 int main() { 33 int n, k; 34 cin >> n >> k; 35 dp[0][0] = "1"; 36 for (int i = 1; i <= k; i++) { 37 fill(dp[1], dp[1] + 1001, "0"); 38 for (int j = 0; j < i; j++) dp[1][j] = dp[0][j]; 39 for (int j = i; j <= n; j++) dp[1][j] = add(dp[1][j - i], dp[0][j]); 40 swap(dp[0], dp[1]); 41 } 42 cout << dp[0][n]; 43 }View Code
需稍加思考的题目
POJ 1065 给出N个矩形，长度递增且宽度递增的一组矩形可以划在一起，求最小组数
贪心
1 #include <algorithm> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 6 struct inf { 7 int l, w; 8 } stick[5001]; 9 10 bool cmp(inf x, inf y) { return x.l < y.l; } 11 12 int vis[5005]; 13 14 int main() { 15 int t, n, x, y; 16 cin >> t; 17 while (t--) { 18 cin >> n; 19 for (int i = 0; i < n; i++) { 20 cin >> stick[i].l >> stick[i].w; 21 } 22 sort(stick, stick + n, cmp); 23 memset(vis, 0, sizeof(vis)); 24 int sum = -1, t; 25 do { 26 t = 0; 27 for (int i = 0; i < n; i++) { 28 if (!vis[i] && (t == 0 || t <= stick[i].w)) { 29 t = stick[i].w; 30 vis[i] = 1; 31 } 32 } 33 sum++; 34 } while (t); 35 cout << sum << "\n"; 36 } 37 }View Code
POJ 1631 给出n组连线（二分图的形状），求其中最大的互不交叉的子集
以左边为基准时，子集对应的右边的序号应该是递增的。所以问题转化为最大上升子序列
1 #include <algorithm> 2 #include <cstdio> 3 #include <iostream> 4 using namespace std; 5 6 int c[40005]; 7 int dp[40005]; 8 9 int main() { 10 int n, a; 11 scanf("%d", &n); 12 while (n--) { 13 scanf("%d", &a); 14 for (int i = 0; i < a; i++) scanf("%d", c[i]); 15 fill(dp, dp + a, 0x7f7f7f7f); 16 for (int i = 0; i < a; i++) { 17 *lower_bound(dp, dp + a, c[i]) = c[i]; 18 } 19 printf("%d\n", lower_bound(dp, dp + a, 0x7f7f7f7f) - dp); 20 } 21 }View Code
POJ 3666 给出一个序列，可以对某一个数字+1/-1的调整，最终使序列不增/不减。求最小代价（测试数据不严格，只要处理不减的情况就可以过）
好题目。dp[i][j]的意义是 使前i个数都降到比第j大的数小于或者等于 并且这个字串是不减的 的 代价
状态转移时，考虑前n个数，要么全比第j-1小，要么至少有一个数(第i个)变成第j大；前者即dp[i][j-1]，后者是dp[i-1][j]+es[j]-a[i]
1 #include <algorithm> 2 #include <cstdio> 3 #include <iostream> 4 using namespace std; 5 6 #define ll long long 7 8 ll dp[2005]; 9 10 int n, a[2005], es[2005]; 11 12 ll min(ll a, ll b) { return a < b ? a : b; } 13 14 int main() { 15 scanf("%d", &n); 16 for (int i = 0; i < n; i++) { 17 scanf("%d", &a[i]); 18 es[i] = a[i]; 19 } 20 sort(es, es + n); 21 for (int i = 0; i < n; i++) { 22 for (int j = 0; j < n; j++) { 23 if (a[i] >= es[j]) 24 dp[j] += a[i] - es[j]; 25 else 26 dp[j] = min(dp[j - 1], dp[j] + es[j] - a[i]); 27 } 28 } 29 printf("%lld\n", dp[n - 1]); 30 }View Code
POJ 2392 给出N种石头的高度，数量，最高能出现的高度。要求能垒成的最高高度
好题目。带限制的多重部分和
1 #include <algorithm> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 8 struct node { 9 int h, a, c; 10 bool operator<(const node &o) const { return a < o.a; } 11 } s[405]; 12 13 int dp[40005], k; 14 15 int main() { 16 scanf("%d", &k); 17 for (int i = 0; i < k; i++) scanf("%d %d %d", &s[i].h, &s[i].a, &s[i].c); 18 sort(s, s + k); 19 memset(dp, -1, sizeof(dp)); 20 dp[0] = 0; 21 for (int i = 0; i < k; i++) { 22 for (int j = 0; j < s[i].h; j++) 23 if (dp[j] >= 0) dp[j] = s[i].c; 24 for (int j = s[i].h; j <= s[i].a; j++) { 25 if (dp[j] >= 0) 26 dp[j] = s[i].c; 27 else if (dp[j - s[i].h] > 0) 28 dp[j] = dp[j - s[i].h] - 1; 29 else 30 dp[j] = -1; 31 } 32 } 33 for (int i = s[k - 1].a; i >= 0; i--) 34 if (dp[i] >= 0) { 35 printf("%d\n", i); 36 exit(0); 37 } 38 }View Code
POJ 2184 N个元素，各有两个关键字；选取若干个使得每个关键字和非负且使总和尽可能大
有负值的背包问题（对两个关键字和DP时 常数是 对第二关键字DP 的2倍，会T）（因为OJ比较老，其实问题不大）
1 #include <algorithm> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 8 const int shift = 1e5; 9 int dp[2][200005]; 10 11 int n, ts, tf, res; 12 13 int main() { 14 memset(dp[0], 128, sizeof(dp[0])); 15 memset(dp[1], 128, sizeof(dp[1])); 16 17 dp[0][shift] = 0; 18 19 scanf("%d", &n); 20 21 for (int i = 0; i < n; i++) { 22 scanf("%d %d", &ts, &tf); 23 if (ts <= 0 && tf <= 0) continue; 24 for (int j = max(0, ts); j <= (int)2e5 + min(0, ts); j++) { 25 dp[1][j] = max(dp[0][j], dp[0][j - ts] + tf); 26 } 27 for (int j = 0; j < max(0, ts); j++) dp[1][j] = dp[0][j]; 28 for (int j = (int)2e5 + min(0, ts) + 1; j <= (int)2e5; j++) 29 dp[1][j] = dp[0][j]; 30 swap(dp[0], dp[1]); 31 } 32 for (int i = shift; i <= (int)2e5; i++) { 33 if (dp[0][i] >= 0) res = max(res, i - shift + dp[0][i]); 34 } 35 printf("%d\n", res); 36 }View Code
END
更多精彩
