The map is a line, which has n unit length. We can build only one
tower on each unit length. The enemy takes t seconds on each unit length. And
there are 3 kinds of tower in this game: The red tower, the green tower and the
blue tower.
The red tower damage on the enemy x points per second when
he passes through the tower.
The green tower damage on the enemy y points
per second after he passes through the tower.
The blue tower let the
enemy go slower than before (that is, the enemy takes more z second to pass an
unit length, also, after he passes through the tower.)
Of course, if you
are already pass through m green towers, you should have got m*y damage per
second. The same, if you are already pass through k blue towers, the enemy
should have took t + k*z seconds every unit length.
FSF now wants to know
the maximum damage the enemy can get.
The first line
contains an integer T (T<=100), indicates the number of cases.
Each
test only contain 5 integers n, x, y, z, t (2<=n<=1500,0<=x, y,
z<=60000,1<=t<=3)
where C indicates the case number and counts from 1. Then output the answer. For
each test only one line which have one integer, the answer to this
question.
#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
typedef __int64 LL;
const int ms=;
LL dp[ms][ms];
LL max(LL a,LL b)
{
return a>b?a:b;
}
int main()
{
LL ans,b,c;//注意 b和c 要定义为LL，因为后面的计算中含有LL形的数。
int T,p=;
int n,x,y,z,t;
scanf("%d",&T);
//cin>>T;
while(T--)
{
printf("Case #%d: ",p++);
//cout<<"Case #"<<p++<<": ";
scanf("%d%d%d%d%d",&n,&x,&y,&z,&t);
//cin>>n>>x>>y>>z>>t;
memset(dp,,sizeof(dp));
ans=x*n*t;
for(b=;b<=n;b++)
for(c=;c+b<=n;c++)
{
dp[b+][c]=max(dp[b+][c],dp[b][c]+c*y*(t+b*z));
dp[b][c+]=max(dp[b][c+],dp[b][c]+c*y*(t+b*z));
ans=max(ans,dp[b][c]+(n-b-c)*x*(t+b*z)+(n-b-c)*y*c*(t+b*z));
}
printf("%I64d\n",ans);
//cout<<ans<<endl;
}
return ;
}