HDU

题意：

人有100血和100魔法，每秒增加 t 魔法(不能超过100)。n个技能，每个技能消耗a[i]魔法值，造成b[i]伤害。普通攻击不消耗魔法，每秒1伤害。

题解：

dp[i][j]在第i秒，魔法值还有j的时候Boss的最少血量

dp转移方程：

dp[i+1][temp]=min(dp[i][j]-b[k],dp[i+1][temp]);

那么我们就要确定人最多能承受Boss伤害多少秒

可以通过下面这个来确定：

int time=100/q+(100%q?1:0);

然后就是暴力dp，第一重for循环枚举时间i，第二重for循环枚举魔法值j，第三重for循环枚举技能

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<math.h>
 6 #include<vector>
 7 #include<queue>
 8 #include<stack>
 9 #include<map>
10 using namespace std;
11 typedef long long LL;
12 const int maxn=105;
13 const LL MAX=1e15;
14 const int INF=0x3f3f3f3f;
15 const double eps=1e-8;
16 const double PI=3.1415926;
17 const int mod = 1e9+7;
18 typedef long long LL;
19 int dp[maxn][maxn],a[maxn],b[maxn];
20 int main()
21 {
22     int n,t,q,ans;
23     while(~scanf("%d%d%d",&n,&t,&q) && n+t+q)
24     {
25         int flag=0;
26         a[0]=0;
27         b[0]=1;
28         for(int i=1; i<=n; ++i)
29             scanf("%d%d",&a[i],&b[i]);
30         memset(dp,-1,sizeof(dp));
31         dp[0][100]=100;
32         int time=100/q+(100%q?1:0);
33         ans=-1;
34         for(int i=0; i<time; ++i)
35         {
36             for(int j=100; j>=0; --j)
37             {
38                 if(dp[i][j]>0)
39                 {
40                     for(int k=0; k<=n; ++k)
41                     {
42                         if(j>=a[k])
43                         {
44                             int temp=j-a[k]+t;
45                             if(temp>100) temp=100;
46                             if(dp[i+1][temp]>dp[i][j]-b[k] || dp[i+1][temp]==-1)
47                             {
48                                 dp[i+1][temp]=dp[i][j]-b[k];
49                                 if(dp[i+1][temp]<=0)
50                                 {
51                                     //printf("%d %d %d 
",time,dp[i+1][temp],i+1);
52                                     ans=i+1;
53                                     flag=1;
54                                     break;
55                                 }
56                             }
57                         }
58                     }
59                 }
60                 if(flag) break;
61             }
62             if(flag) break;
63         }
64         if(flag)
65         {
66             printf("%d
",ans);
67         }
68         else printf("My god
");
69     }
70     return 0;
71 }