问题描述
【Description】
卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D (2 <= D <= 100)英尺。
卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t(0
这道题可以用DP解决。用l[i,j]表示掉下来i个垃圾后，卡门爬上的高度为j时她最长的寿命。显然l[0,0]=10。对于任一个状态l[i-1,j]，若l[i-1,j]>=g[i].time，说明这个状态的卡门能够坚持到下一个垃圾下落。在这种情况下，按以下两种方法处理第i个垃圾，即进行状态转移：
吃掉第i个垃圾，即update(l[i,j],l[i-1,j]+g[i].life)；
用第i个垃圾来垫高。令t=j+g[i].height，即把第i个垃圾用来垫高后卡门爬上的总高度。如果t>=d，则卡门于g[i].time时爬了出来，否则update(l[i,t],l[i-1,j])。
若首次遇到某一个l[i,0]一次也没有赋值，说明卡门不可能坚持到第i个垃圾下落，则她最多可以存活的时间为l[i-1,0]（即把前i-1个垃圾全吃掉后的寿命）。
注意到在计算l数组的第i行时只用到了第i-1行，因此l数组可用滚动数组来实现。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <stdio.h> #include <string.h> #define MAXN 101 #define max(a,b) a>b?a:b typedef struct node { int time, life, height; }node; int main() { node a[MAXN], temp; int flag; int f[MAXN][MAXN * 10]; int n, d, i, j, k, t, maxt, m; scanf("%d%d", &d, &n); maxt = 0; for (i = 1; i <= n; i++) { scanf("%d%d%d", &a[i].time, &a[i].life, &a[i].height); } for (i = 1; i < n; i++) { for (j = i + 1; j <= n; j++) { if (a[i].time > a[j].time) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } } memset(f, 0, sizeof(f)); f[0][0] = 10; flag = 0; maxt = 0; for (i = 1; i <= n; i++) { m = 0; k = 0; for (j = 0; j <= maxt; j++) { if (f[i - 1][j] >= a[i].time) { f[i][j] = max(f[i][j], f[i - 1][j] + a[i].life); t = j + a[i].height; if (t >= d) { flag = a[i].time; break; } if (t > m) m = t; f[i][t] = max(f[i][t], f[i - 1][j]); k++; } } if (k == 0) break; if (flag != 0) break; maxt = m; } if (flag != 0) printf("%d\n", flag); else { printf("%d\n", f[i - 1][0]); } return 0; } |
应该是5年前的代码了，从以前的百度blog中转了过来