NOIP模拟题 LGTB 玩THD [DP]

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

将小兵血量转化成“时间”，用La Tour 与 L’Homme 表示要打多少次，注意处理整除情况！！

相当于第二维表示可以领先La Tour 多少步

特别要注意处理初始化！！！！ 有些状态不存在的一定要确保不会用到才不赋初值-INF ！！！

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smin(x,tmp) x=min((x),(tmp))
#define smax(x,tmp) x=max((x),(tmp))
#define cost(i) soldier[i].cost
#define homme(i) soldier[i].homme
#define tour(i) soldier[i].tour
const int INF=0x3f3f3f3f;
const int maxn=105;
int maxhp=1001;
int P,Q,n;
struct Soldier
{int tour,homme;int hp,cost;inline void read(){scanf("%d%d",&hp,&cost);tour = (hp - 1) / Q;homme = (hp - tour * Q -1) / P + 1;}
}soldier[maxn];
int f[maxn][200/20*maxn<<1];
int main()
{freopen("thd.in","r",stdin);freopen("thd.out","w",stdout);scanf("%d%d%d",&P,&Q,&n);for(int i=1;i<=n;i++) soldier[i].read();for(int i=0;i<=n;i++)for(int j=0;j<=maxhp<<1;j++)f[i][j]=-INF; // not only the visiting following, but also the possible to visited!!!f[0][1]=0; // given one chance at first!!for(int i=1;i<=n;i++)for(int j=0;j<=maxhp;j++){if(j >= tour(i) + 1) smax(f[i][j] , f[i-1][j-(tour(i)+1)]); if(j >= tour(i) - homme(i)) smax(f[i][j] , f[i-1][j- (tour(i) - homme(i))] + cost(i));}printf("%d",*max_element(f[n],f[n]+maxhp+1));//from the 0 !!return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！