題目

Stupid Tower Defense

在坐標軸$[1,n]$上，每兩個相鄰的整數點之間可以放置一座防御塔。

怪物初始時 $t$ 秒移動一個單位。

• 防御塔$1$：在當前線段上的敵人每秒受到$x$傷害。例如在$[1,2)$上放置一座防御塔$1$，怪物在$[1,2)$上行走每秒會受到$x$傷害。

• 防御塔$2$：在當前線段后的敵人每秒受到$y$傷害。例如在$[1,2)$上放置一座防御塔$2$，怪物在$[2,n)$上行走每秒會受到$y$傷害。

• 防御塔$3$：在當前線段后的敵人被減速$z$。例如在$[1,2)$上放置一座防御塔$3$，怪物在$[2,n)$上行走會被減速$z$，也就是$t=t+z$。

防御塔2/3的效果可以疊加。

數據范圍 （2<=n<=1500 , 0<=x,y,z<=60000 1<=t<=3）

問一個敵人從$1$走到$n$受到的最大傷害是多少。

解題思路

經過一點分析，顯然有防御塔1肯定是連續的放置在最后面一段區間。

令$DP[i][j]$為前$i$個防御塔，放置$j$個防御塔$2$、$i?j$個防御塔$3$的最大傷害，$i$后面全為防御塔$3$。這時候，前面防御塔2/3的排列順序對后面的貢獻無影響。只記錄數量即可。

因此有狀態轉移方程：

dp[i][j] = dp[i-1][j] + V1; dp[i][j] = dp[i-1][j-1] + V2; ans = max(ans , dp[i][j] + 后面全為防御塔1的價值)

AC代碼

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <unordered_map> #include <map> #include <vector> using namespace std;const int N = 1505; long long dp[N][N]; //前i個有j個減速 i-j個后攻 int CA; void solve() {memset(dp, 0, sizeof dp);long long n, x, y, z, t;scanf("%lld %lld %lld %lld %lld", &n, &x, &y, &z, &t);long long ans = t * x * n;long long a = 1, b = 0, len = n - 1; //a減速 b后攻 c行程ans = max(ans, (a * z + t) * (b * y + x) * len);a = 0, b = 1, len = n - 1;ans = max(ans, (a * z + t) * (b * y + x) * len);dp[1][0] = 0;dp[1][1] = 0;for (int i = 2; i <= n; i++){for (int j = 0; j <= i; j++){if (!j){dp[i][j] = max(dp[i][j], dp[i - 1][j] + (i - 1) * y * t);long long a = 0, b = i, len = n - i; //a減速 b后攻ans = max(ans, dp[i][j] + (a * z + t) * (b * y + x) * len);}else{//當前放減速long long T = t + (j - 1) * z;long long D = ((i - 1) - (j - 1)) * y;dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + T * D); //當前放減速long long a = j, b = i - j, len = n - i; //a減速 b后攻ans = max(ans, dp[i][j] + (a * z + t) * (b * y + x) * len);//當前放后攻，dp[i][j]從dp[i-1][j]轉移 因此只有i!=j 當前才能放后攻if (i != j){T = t + j * z;D = ((i - 1) - j) * y;dp[i][j] = max(dp[i][j], dp[i - 1][j] + T * D); //當前放后攻a = j, b = i - j, len = n - i; //a減速 b后攻ans = max(ans, dp[i][j] + (a * z + t) * (b * y + x) * len);}}}}printf("Case #%d: %lld\n", ++CA, ans); } int main() {int t;cin >> t;while (t--)solve();return 0; }

總結

以上是生活随笔為你收集整理的hdu4939思维DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。