Stupid Tower Defense
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 151 Accepted Submission(s): 32
Problem Description
FSF is addicted to a stupid tower defense game. The goal of tower defense games is to try to stop enemies from crossing a map by building traps to slow them down and towers which shoot at them as they pass.
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 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.
Input
There are multiply test cases.
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)
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)
Output
For each case, you should output "Case #C: " first, 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.
Sample Input
1
2 4 3 2 1
2 4 3 2 1
Sample Output
Case #1: 12
Hint
For the first sample, the first tower is blue tower, and the second is red tower. So, the total damage is 4*(1+2)=12 damage points.
Author
UESTC
Source
思路：红塔放在最后，绿塔和蓝塔dp
注意：绿塔和蓝塔的效果都是延迟的，当前塔没有效果，要到下一格。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue> #define N 1505
#define M 105
#define mod 1000000007
#define mod2 100000000
#define ll long long
#define maxi(a,b) (a)>(b)? (a) : (b)
#define mini(a,b) (a)<(b)? (a) : (b) using namespace std; ll i,j;
ll n;
int T;
ll x,y,z,t;
ll ans;
ll te;
ll k,m,p;
ll dp[N][N]; int main()
{
freopen("data.in","r",stdin);
scanf("%d",&T);
for(int cnt=;cnt<=T;cnt++)
{ memset(dp,,sizeof(dp));
scanf("%I64d%I64d%I64d%I64d%I64d",&n,&x,&y,&z,&t);
ans=;
for(i=;i<=n;i++){
for(k=;k<=i;k++){
m=i-k;p=n-m-k;
if(k==){
if(m==) ans=max(ans,t*n*x);
else{
dp[m][k]=dp[m-][k]+(t+k*z)*(m-)*y;
ans=max(ans,dp[m][k]+p*(t+k*z)*(x+m*y));
}
}
else{
if(m==){
dp[m][k]=dp[m][k-]+(t+(k-)*z)*m*y;
ans=max(ans,dp[m][k]+p*(t+k*z)*(x+m*y));
}
else{
dp[m][k]=max(dp[m-][k]+(t+k*z)*(m-)*y,dp[m][k-]+(t+(k-)*z)*m*y);
ans=max(ans,dp[m][k]+p*(t+k*z)*(x+m*y));
}
} }
}
printf("Case #%d: %I64d\n",cnt,ans);
}
return ;
}