程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4939 Stupid Tower Defense(貪心+dp)

HDU 4939 Stupid Tower Defense(貪心+dp)

編輯:C++入門知識

HDU 4939 Stupid Tower Defense(貪心+dp)


HDU Stupid Tower Defense

題目鏈接

題意:有一些塔,紅塔能攻擊經過他的,綠塔能攻擊經過之後的,藍塔能把經過之後的減速,求在1-n上放塔,求傷害最大值

思路:一開始以為直接貪心,綠塔最前,藍塔中間,紅塔最後就可以了,結果其實是錯的

不過,紅塔放最後是肯定的,這個很顯然就不多證明了,是貪心的思想
然後就dp[i][j]表示放到i,前面有j個綠塔去狀態轉移即可

代碼:

#include 
#include 
#include 
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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved