# Stupid Tower Defense

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1589    Accepted Submission(s): 452

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

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.

red               经过这个塔的时候，收到 x  (d / s) 的伤害

green           经过这个塔之后 ， 受到 y (d / s) 的持续伤害

bule             经过这个塔之后 ， 经过1个塔的时间增加 z 秒

dp[i][j] 。。。表示前  i + j  (<=n ) 个长度   i 个放green ， j 个放blue 所得到的最大伤害 。

dp[i][j] = max( dp[i-1][j] + ( j * z + t ) * y * ( i - 1 ) , dp[i][j-1] + ( ( j - 1 ) * z + t ) * y * i );

```#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1550 ;

ll dp[N][N];   // i = green , j = blue ...

int main()

{
ll _ , n , x , y , z , t , cas = 1;
#ifdef LOCAL
freopen("in","r",stdin);
#endif
cin >> _ ;
while( _ -- ){
cin >> n >> x >> y >> z >> t ;
cout << "Case #"<< cas++ <<": ";

memset(dp,0,sizeof dp);

for( int i = 1 ; i <= n ; ++i ){
for( int j = 0 ; j <= i ; ++j ){
int k = i - j ;
ll temp = 0 ;
if( j > 0 ) temp = max( temp , dp[j-1][k] + ( k * z  + t ) * y * ( j - 1 )  );
if( k > 0 ) temp = max( temp , dp[j][k-1] + ( ( k - 1 ) * z + t ) * y * j ) ;
dp[j][k] = temp ;
}
}

ll ans = 0 ;
for( int i = 0 ; i <= n ; ++i ){
for( int j = 0 ; j + i <= n ; ++j ){
ans = max ( ans , dp[i][j] + ( n - i - j ) * ( x * ( t + z * j ) + i * y * ( t + z * j ) ) );
}
}
cout << ans << endl ;
}
return 0;
}```

## HDOJ 4939 Stupid Tower Defense

red放到后面显然更优,dp[i][j]表示前i个塔里有j个blue,最后枚举有多少个red Stupid Tower Defense Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 599    Accepted Submission(s): 163 Problem Description FSF is addicted to

## HDOJ题目4939 Stupid Tower Defense（dp）

Stupid Tower Defense Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1759    Accepted Submission(s): 498 Problem Description FSF is addicted to a stupid tower defense game. The goal of tower

## hdu4939 Stupid Tower Defense （DP）

2014多校7 第二水的题 4939 Stupid Tower Defense Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 366    Accepted Submission(s): 88 Problem Description FSF is addicted to a stupid tower defense game.

## hdu 4779 Tower Defense （思维+组合数学）

Tower Defense Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 474    Accepted Submission(s): 126 Problem Description DRD loves playing computer games, especially Tower Defense games. Tower De