hdu 4939 Stupid Tower Defense

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;
}
时间: 10-08

hdu 4939 Stupid Tower Defense的相关文章

hdu 4939 Stupid Tower Defense ( dp )

题目链接 题意:给出一条长为n个单位长度的直线,每通过一个单位长度需要t秒. 有3种塔,红塔可以在当前格子每秒造成x点伤害,绿塔可以在之后的格子每秒造成y点伤害, 蓝塔可以使通过单位长度的时间增加z秒.问如何安排3种塔的顺序使得造成的伤害最大,输出最大伤害值. 分析:比赛的时候实在是没有想出来有三种不同的 塔,每种塔的作用不同,怎么dp.看题解才知道,应该把 所有的红塔放到最后面,因为直线的长度是一定的,而红塔在前面不会增加后面的伤害,然后问题就是如何安排 绿塔和蓝塔,我这里d[i][j]代表前

2014多校第七场1005 || HDU 4939 Stupid Tower Defense (DP)

题目链接 题意 :长度n单位,从头走到尾,经过每个单位长度需要花费t秒,有三种塔: 红塔 :经过该塔所在单位时,每秒会受到x点伤害. 绿塔 : 经过该塔所在单位之后的每个单位长度时每秒都会经受y点伤害. 蓝塔 : 经过该塔所在单位之后,再走每个单位长度的时候时间会变成t+z. 思路 : 官方题解 : 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define LL long long

hdu 4939 Stupid Tower Defense 动态规划

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4939 塔防游戏 红塔绿塔蓝塔 当年我队友在不知道红塔必须放最后这个结论的情况下把这道题做出来了现在我细思恐极 仰慕至极Orz 写出来不是很难的题目 但是仔细想想 还是有很多值得推敲的地方 下面证明一下这个“常识” 反证法 a.如果得到一个最优解 然后在这个最优解中有一个红塔在一个绿塔前面 那么把这两个塔交换一下位置 必定可以得到一个更优的解 与假设的“当前是最优解”矛盾 b.如果得到一个最优解 然后

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)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4939 Stupid Tower Defense Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 493    Accepted Submission(s): 129 Problem Description FSF is addicte

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

Stupid Tower Defense

题目链接 题意: 水平方向上n个1*1的格子,每个格子内部可以种一个植物,经过一个格子的时间为t.一共三种植物:R植物,经过时每秒收到r点伤害:G植物,经过后每秒受到g点伤害:B植物,经过后经过一个格子的时间加上b 2<=n<=1500,0<=r, g, b<=60000,1<=t<=3 分析: 最开始考虑的贪心:先B植物,后G植物,最后B植物,后来才发现是错误的. 首先明白,R植物对答案的影响和位置无关,而B和G植物越早种越好,所以问题就在于B和G的种法上. 状态表示