首页 > 代码库 > HDU 4939 Stupid Tower Defense(贪心+dp)

HDU 4939 Stupid Tower Defense(贪心+dp)

HDU Stupid Tower Defense

题目链接

题意:有一些塔,红塔能攻击经过他的,绿塔能攻击经过之后的,蓝塔能把经过之后的减速,求在1-n上放塔,求伤害最大值

思路:一开始以为直接贪心,绿塔最前,蓝塔中间,红塔最后就可以了,结果其实是错的

不过,红塔放最后是肯定的,这个很显然就不多证明了,是贪心的思想
然后就dp[i][j]表示放到i,前面有j个绿塔去状态转移即可

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1505;

typedef long long ll;
int T;
ll n, x, y, z, t;
ll dp[N][N];

ll solve() {
    ll ans = n * x * t;
    dp[0][0] = 0;
    for (ll i = 1; i <= n; i++) {
	for (ll j = 0; j <= i; j++) {
	    dp[i][j] = 0;
	    if (j != i)
		dp[i][j] = max(dp[i][j], dp[i - 1][j] + y * j * (t + (i - j - 1) * z));
	    if (j)
		dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + y * (j - 1) * (t + (i - j) * z));
	    ans = max(ans, dp[i][j] + (t + (i - j) * z) * (n - i) * (x + y * j));
	}
    }
    return ans;
}

int main() {
    int cas = 0;
    scanf("%d", &T);
    while (T--) {
	scanf("%I64d%I64d%I64d%I64d%I64d", &n, &x, &y, &z, &t);
	printf("Case #%d: %I64d\n", ++cas, solve());
    }
    return 0;
}