LGTB 玩THD

LGTB 最近在玩一個(gè)類似DOTA 的游戲名叫THD
有一天他在守一座塔，對(duì)面的N 個(gè)小兵排成一列從近到遠(yuǎn)站在塔前面
每個(gè)小兵有一定的血量hi，殺死后有一定的金錢gi
每一秒，他都可以攻擊任意一個(gè)活著的小兵，對(duì)其造成P 點(diǎn)傷害，如果小兵的血量低于1 點(diǎn)，小兵死亡，他
得到金錢。他也可以不攻擊任何小兵。
每一秒LGTB 攻擊完畢之后，塔會(huì)攻擊距離塔最近的一個(gè)活著的小兵，對(duì)其造成Q 點(diǎn)傷害，如果小兵的血
量低于1 點(diǎn)，小兵死亡，LGTB 不會(huì)得到金錢
現(xiàn)在LGTB 想知道，在他選擇最優(yōu)策略時(shí)，他能得到多少錢。
輸入
輸入第一行包含3 個(gè)整數(shù)P, Q, N
接下來N 行，每行包含2 個(gè)整數(shù)hi, gi
第i 個(gè)小兵和塔之間的距離為i
輸入的意義如題面所示
對(duì)于20% 的數(shù)據(jù)，1 N 4
對(duì)于50% 的數(shù)據(jù)，1 N 20
對(duì)于100% 的數(shù)據(jù)，20 P,Q 200, 1 N 100, 1 hi 200, 0 gi 106
輸出
輸出包含一個(gè)整數(shù)W，代表LGTB 最多能獲得的金錢

樣例輸入
20 60 3
80 100
80 200
120 300

樣例輸出
500

?

將小兵血量轉(zhuǎn)化成“時(shí)間”，用La Tour 與 L'Homme 表示要打多少次，注意處理整除情況！！

相當(dāng)于第二維表示可以領(lǐng)先La Tour 多少步

特別要注意處理初始化！！！！ 有些狀態(tài)不存在的一定要確保不會(huì)用到才不賦初值-INF ！！！

AC代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #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; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/ourfutr2330/p/5671453.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[DP] LGTB 玩THD （复杂状态DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。