首页 > 代码库 > 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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。