首页 > 代码库 > hdu 4939 Stupid Tower Defense(dp)

hdu 4939 Stupid Tower Defense(dp)

题目链接:hdu 4939 Stupid Tower Defense

题目大意:塔防游戏,一个长度为n的路,给定x,y,z和t。然后对应每个长度的位置可以放攻击塔,有三种:

  • 红塔:怪在红塔所单位长度内每秒受到x点伤害。
  • 绿塔:怪经过绿塔之后,每秒受到y点伤害。
  • 蓝塔:怪经过后每走一格的时间加上z。
    求最大伤害。

解题思路:更具塔的性质,红塔肯定放在最后,所以有dp[i][j]表示到第i个位置,放j个蓝塔造成的伤害值最大为多少。并且过程中维护ans最大(要加上后面红塔的攻击伤害),对于一个状态dp[i][j],除了转移到dp[i+1][j]和dp[i+1][j+1]之外,可以将后面n-i个位置视为放红塔,去维护ans。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef unsigned long long ll;
const int maxn = 1505;

int N;
ll x, y, z, T;
ll dp[maxn][maxn];

ll solve () {
    ll ans = 0;
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < N; i++) {

        for (int j = 0; j <= i; j++) {
            ll v = (T + j * z);
            ll w = v * (i-j) * y;
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + w);
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + w);
            ans = max(ans, dp[i][j] + (x * v + w) * (N-i));
        }
    }

    for (int i = 0; i <= N; i++)
        ans = max(ans, dp[N][i]);
    return ans;
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        scanf("%d%I64u%I64u%I64u%I64u", &N, &x, &y, &z, &T);
    //    scanf("%d%lld%lld%lld%lld", &N, &x, &y, &z, &T);
    //    printf("Case #%d: %lld\n", kcas, solve());
        printf("Case #%d: %I64u\n", kcas, solve());
    }
    return 0;
}