投資遊戲

https://zerojudge.tw/ShowProblem?problemid=m373

題意

求最大連續子序列合，但可以跳過 $k$ 個元素

想法

在不考慮 $k$ 的情況下
這是一個非常經典的問題
解法的話也非常多元
以現在這題來說 Kadane's Algorithm 應該會是比較好做的

那如果把 $k$ 的條件加進去呢？
把測資範圍仔細讀過之後可以注意到 $k \leq 20$
考慮動態規劃的作法
我們定義 $dp[i]$ 為考慮陣列前 $i$ 個元素的最佳解
然後我們可以往前跳過不超過 $k$ 個
因此 $dp[i]$ 可以從 $dp[i-1]、dp[i-2] \cdots dp[i-k-1]$ 轉移過來取 $max$
但我們還需要紀錄總共已經使用了幾個金牌
所以再開一個維度來維護這個資訊

綜合以上幾點，我們可以推出這樣的轉移式
定義 $dp[i][j]$ 為考慮前 $i$ 個元素且使用 $j$ 個金牌的最佳解
轉移的部份就是 $dp[i][j] = \max(dp[i-1][j-1], dp[i-1][j] + val[i])$
兩個狀態分別代表在第 $i$ 天使用和不使用金牌 \

最後照著轉移式把程式寫出來就好ㄌ

時間複雜度 $O(n \times k)$

考點

• 動態規劃

程式碼

#include <bits/stdc++.h>
#define int long long

using namespace std;

int v[200000];
int dp[200000][30];

signed main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) { // 第 i 天
        cin >> v[i]; // 因為只會依賴到之前的狀態所以可以邊讀入邊做
        for (int j = 0; j <= k; j++) { // 使用 j 個金牌
            if (j > 0) dp[i][j] = dp[i-1][j-1]; // 使用金牌
            dp[i][j] = max(dp[i][j], dp[i-1][j] + v[i]); // 不使用金牌
        }
    }
    int ans = 0;
    // 在所有合法狀態中取得最佳解
    for (int i = 0; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            ans = max({ans, dp[j][i], 0LL});
        }
    }
    cout << ans << endl;
}