Posted on 2010-11-30 15:14
小小菜鸟蛋 阅读(759)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=3008
这道题，从一开始的读错题意到敲代码时犯了很多很低级的错误，纠结了我好久好久，最后还是去看了别人的解题报告，发现自己有个地方想错了。。还从大牛的题解里接触到了try...catch...，果断是个很方便的货~~
死亡时间是一定的，因为每秒都会减少q点LifeValue，所以在死之前把boss给KO掉就行了~~要不然就是My god了。。。
f[ i ][ j ]表示第 i 秒结束时，MagicValue为 j，能消耗boss的最大LifeValue：
int temp = min(100, j-a[k]+t) //因为每次回血后MagicValue最多不会超过100
f[i][temp] = max(f[i][temp], f[i-1][j] + b[k]) //一开始我把方程错写为：f[i][j] = max(f[i][j], f[i-1][temp] + b[k])
01 #include <cstdio>
02 #include <cstring>
03 #include <algorithm>
04 using namespace std;
05
06 const int N = 110;
07 int f[N][N], a[N], b[N];
08
09 int main()
10 {
11 int n, t, q;
12 while(scanf("%d%d%d", &n, &t, &q) != EOF && n + t + q)
13 {
14 memset(a, 0, sizeof(a));
15 memset(b, 0, sizeof(b));
16 a[0] = 0; //把ordinary attack当做第一种攻击
17 b[0] = 1;
18 for (int i = 1; i <= n; i++)
19 scanf("%d%d", &a[i], &b[i]);
20
21 for (int i = 0; i < N; i++)
22 for (int j = 0; j < N; j++)
23 f[i][j] = -99999999; //第一个状态只能由f[0][100]转移过来得到
24 f[0][100] = 0;
25
26 try
27 {
28 for (int i = 1; (i-1)*q < 100; i++)
29 for (int j = 0; j <= 100; j++)
30 for (int k = 0; k <= n; k++)
31 if (j >= a[k])
32 {
33 int temp = min(100, j-a[k]+t);
34 f[i][temp] = max(f[i][temp], f[i-1][j] + b[k]);
35 if (f[i][temp] >= 100)
36 throw i;
37 }
38 printf("My god\n");
39 }
40 catch (int ans)
41 {
42 printf("%d\n", ans);
43 }
44 }
45 }