LGTB 玩THD
LGTB 最近在玩一个类似DOTA 的游戏名叫THD
有一天他在守一座塔，对面的N 个小兵排成一列从近到远站在塔前面
每个小兵有一定的血量hi，杀死后有一定的金钱gi
每一秒，他都可以攻击任意一个活着的小兵，对其造成P 点伤害，如果小兵的血量低于1 点，小兵死亡，他
得到金钱。他也可以不攻击任何小兵。
每一秒LGTB 攻击完毕之后，塔会攻击距离塔最近的一个活着的小兵，对其造成Q 点伤害，如果小兵的血
量低于1 点，小兵死亡，LGTB 不会得到金钱
现在LGTB 想知道，在他选择最优策略时，他能得到多少钱。
输入
输入第一行包含3 个整数P, Q, N
接下来N 行，每行包含2 个整数hi, gi
第i 个小兵和塔之间的距离为i
输入的意义如题面所示
对于20% 的数据，1 N 4
对于50% 的数据，1 N 20
对于100% 的数据，20 P,Q 200, 1 N 100, 1 hi 200, 0 gi 106
输出
输出包含一个整数W，代表LGTB 最多能获得的金钱
样例
样例输入
20 60 3
80 100
80 200
120 300
样例输出
500
解题报告：
这道题先开始是用的深搜，然后忽略了很多情况，样例都没过，却神奇的过了一组数据。
正解是用动规。
这道题还没有完全理解
同学对这道题的解释可能有用：http://blog.csdn.net/u011327397/article/details/51920679
#include<iostream>
#include<cstdio>
using namespace std;
int p,q,n;
struct pp{
int tower,me,hp,money;
};
pp v[];
int f[][]; //time you can get from:100*200/20
int main()
{
freopen("thd.in","r",stdin);
freopen("thd.out","w",stdout);
cin>>p>>q>>n;
for (int i=;i<=n;i++)
{
scanf("%d%d",&v[i].hp,&v[i].money);
v[i].tower=(v[i].hp-)/q;// leave one more time for me
v[i].me=(v[i].hp-v[i].tower*q-)/p+;
// to avoid 23/4=5 +1 =6 and 24/4=6 + 1=7(wrong) so (24-1)/4=5+1=6;
}
for (int i=;i<=n;i++)
for (int j=;j<=;j++)
f[i][j]=-;//if the tower q is > > hp ;
f[][]=;
for (int i=;i<=n;i++)
for (int j=;j<=;j++)//time
{
if (f[i][j+v[i].tower+]<f[i-][j])//not attack and the tower kill it
f[i][j+v[i].tower+]=f[i-][j];
if (j>=v[i].me-v[i].tower)
if (f[i][j-v[i].me+v[i].tower]<f[i-][j]+v[i].money)//the j time you kill it
// may some time you have known how much you get when you just not
//kill it,to compare with this time(j) you kill it how much you get
//choose the max;
f[i][j-v[i].me+v[i].tower]=f[i-][j]+v[i].money;
}
int ans=;
for (int i=;i<=;i++)
if (f[n][i]>ans) ans=f[n][i];
cout<<ans;
return ;
}
可以忽略那些英文注释，人太懒不想从“中”切换“英”，就直接用英文注释了。