首页 > 代码库 > hdu 4939 Stupid Tower Defense

hdu 4939 Stupid Tower Defense

2024-07-26 07:40:19   224人阅读

 

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.
 
 

 

题目给出一条长度为n的直线 ， 你可以在长度为1的单元上面建造塔。

有三种类型的塔 

颜色                  效果

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

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

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

 

题目要求 ， 求出在直线上放置n个塔 ， 使得经过直线后受到的伤害最大。 

 

然后可想而知， 红色无论放多少个。 最后放肯定是没错的 ， 因为能够得到蓝色的叠加时间 ， 伤害效果尽量大。

剩下就是蓝色跟绿色 ， 应该怎么放。

这时候就要用到DP了 。

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 );

 

注意一下边界 。 

然后最后要补上 red 塔的伤害就得出答案了~

 

#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;}

 

hdu 4939 Stupid Tower Defense


联系
我们