思路:用小脑想一想,可以知道红塔一定是放在最后的。
用dp[i][j],代表前i个中j个蓝塔(减速)的情况下前i个可以造成的伤害,然后,这种状态可以推出后n-i个全是红塔的总伤害,取最大。
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #include<map> #include<queue> #include<stack> #include<cmath> using namespace std; long long dp[1511][1511]; int main() { int T; int ca=1; scanf("%d",&T); int n; long long x,y,z,t; while(T--) { scanf("%d%I64d%I64d%I64d%I64d",&n,&x,&y,&z,&t); memset(dp,0,sizeof(dp)); long long ans=(1ll*n)*x*t; for(int i=1;i<=n;i++) { for(int j=0;j<=i;j++) { long long g=i-j; long long b=j; long long r=n-i; if(j==0)dp[i][j]=dp[i-1][j]+t*(g-1)*y; else if(i==j)dp[i][j]=dp[i-1][j-1]+((b-1)*z+t)*g*y; else dp[i][j]=max(dp[i-1][j]+(b*z+t)*(g-1)*y,dp[i-1][j-1]+((b-1)*z+t)*g*y); ans=max(ans,dp[i][j]+r*(x+(g*y))*(z*b+t)); } } printf("Case #%d: %I64d\n",ca++,ans); } return 0; }