//给你三个塔//红塔：敌人过红塔时有每秒x伤害//绿塔：敌人过绿塔后有每秒y伤害//蓝塔：敌人过蓝塔后过每一格时间增加z//问敌人过n个格造成最大伤害//很容易想到红塔必然放最后//所以对于每一格的选择只有蓝塔和红塔//用dp[i][j]表示对于前i格选了j个蓝塔//dp[i][j] = max(dp[i-1][j] + (i-1-j)*y*(t+j*z) , dp[i-1][j-1] + (i-j)*y*(t+(j-1)*z)) ;//然后 ans = max(ans , dp[i][j] + (j*z+t)*(n-i)*(x + (i-j)*y));#include<cstdio>#include<cstring>#include<iostream>using namespace std ;const int maxn = 1515;typedef __int64 ll ;ll dp[maxn][maxn] ;int main(){ int T ; scanf("%d" ,&T) ; int cas = 0 ; while(T–) { ll n , x , y , z , t ; scanf("%I64d%I64d%I64d%I64d%I64d" ,&n , &x , &y , &z ,&t) ; memset(dp , 0 , sizeof(dp)) ; ll ans = n*x*t; for(ll i = 1;i <= n;i++) for(ll j = 0;j <= i;j++) { if(j == 0)dp[i][j] = dp[i-1][j] + (i-1-j)*y*(t+j*z) ; else dp[i][j] = max(dp[i-1][j] + (i-1-j)*y*(t+j*z) , dp[i-1][j-1] + (i-j)*y*(t+(j-1)*z)) ; ans = max(ans , dp[i][j] + (j*z+t)*(n-i)*(x + (i-j)*y)); } printf("Case #%d: ",++cas) ; printf("%I64d\n",ans) ; } return 0;}
，旅行，不要害怕错过什么，
