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.

 

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)

 

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

 

Sample Output

 

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 ;

 }