題目鏈接
題意：有一些塔，紅塔能攻擊經過他的，綠塔能攻擊經過之後的，藍塔能把經過之後的減速，求在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; }
