給你一段長(zhǎng)為n的路，每一個(gè)單位長(zhǎng)度可以放一種塔，這里有三種塔。

紅1）對(duì)正在經(jīng)過這座塔的敵人進(jìn)行 x 每秒傷害的攻擊

綠2）對(duì)于已經(jīng)經(jīng)過這塔的敵人進(jìn)行y每秒的傷害攻擊

藍(lán)3）對(duì)已經(jīng)經(jīng)過這個(gè)塔的敵人放慢速度，使得原先為 經(jīng)過一個(gè)單位時(shí)間為 ?t的速度變?yōu)??t+z

對(duì)于紅塔一定是放在最后面，然后對(duì)于前面的綠塔和藍(lán)塔DP

dp[i][j]=Max(dp[i-1][j-1]+y*(i-j)*(t+(j-1)*z),dp[i-1][j]+y*(i-j-1)*(t+j*z));?

?前i個(gè)放j個(gè)藍(lán)塔=Max（（前i-1個(gè)放j-1個(gè),當(dāng)前放藍(lán)塔所得到的傷害總和），（前i-1個(gè)放j個(gè)，當(dāng)前放綠塔得到的傷害總和））；

#include "stdio.h" #include "string.h" __int64 dp[1600][1600]; __int64 Max(__int64 a,__int64 b) {if (a<b) return b;else return a; } int main() {__int64 Case,ii,n,x,y,z,t,ans,i,j;scanf("%I64d",&Case);for (ii=1;ii<=Case;ii++){scanf("%I64d%I64d%I64d%I64d%I64d",&n,&x,&y,&z,&t);printf("Case #%I64d: ",ii);memset(dp,0,sizeof(dp));for (i=0;i<=n;i++) //前i個(gè)位置for (j=0;j<=i;j++) // 放j個(gè)藍(lán)塔{if (j==0) dp[i][j]=dp[i-1][j]+y*(i-j-1)*(t+j*z);elsedp[i][j]=Max(dp[i-1][j-1]+y*(i-j)*(t+(j-1)*z),dp[i-1][j]+y*(i-j-1)*(t+j*z));if (dp[i][j]<0) dp[i][j]=0;}ans=0;for (i=0;i<=n;i++)for (j=0;j<=i;j++)ans=Max(ans,dp[i][j]+(n-i)*(t+j*z)*(x+y*(i-j)));printf("%I64d\n",ans);}return 0; }

? ? ? ? ? ? ? ??

總結(jié)

以上是生活随笔為你收集整理的HDU 4939 DP的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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