题意要搞清楚。。。。
绿塔是持续伤害,红塔是瞬时伤害。
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define maxn 2000 #define ll __int64 ll dp[maxn][maxn]; //dp[i][j]表示前i个位置(包括当前位置)有j个蓝塔。 ll n,x,y,z,t; int main() { int T,cas=1; scanf("%d",&T); while(T--) { scanf("%I64d%I64d%I64d%I64d%I64d",&n,&x,&y,&z,&t); memset(dp,0,sizeof(dp)); ll ans=n*t*x; //初始化,全都是红塔 for(ll i=1;i<=n;i++) for(ll j=0;j<=i;j++) { if(j==0) dp[i][j]=dp[i-1][j]+t*(i-j-1)*y; //算是初始化吧,在i个位置之前一个蓝塔都没有,那么都是绿塔,则当前的值为上个状态加上通过当前位置赋予的伤害 else dp[i][j]=max(dp[i-1][j]+(j*z+t)*(max(0LL,i-1-j))*y,dp[i-1][j-1]+((j-1)*z+t)*(i-j)*y); //当前位置的两种选择,放蓝塔和不放蓝塔(放绿塔) ans=max(ans,dp[i][j]+(n-i)*(j*z+t)*(x+(i-j)*y)); } printf("Case #%d: %I64d\n",cas++,ans); } return 0; }