HDU 4939 Stupid Tower Defense(욕심+dp)

1517 단어

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
", ++cas, solve()); } return 0; }

좋은 웹페이지 즐겨찾기