ZeroJudge 解題筆記：g424.PF.抱ㄌㄌ

作者：王一哲
日期：2026年9月14日


ZeroJudge 題目連結：g424.PF.抱ㄌㄌ

解題想法

出題者原來的敘述可能會引起一些問題，我稍微修改一下。假設一列石頭共有 $n$ 顆，長度為 $n$ 的陣列 $nums$ 代表這列石頭的分數，可以從左到右取依序拿走石頭，最多一次只能連續拿 $k$ 顆石頭，求最大總分為何？

這題雖然被分類在基礎題庫，但其實一點也不像基礎題。這題如果按照題目的要求很難寫程式，反過來思考會比較好寫。最多一次只能連續拿 $k$ 顆石頭，相當於在長度為 $k+1$ 的範圍內至少要捨棄 $1$ 個石頭，因此題目所求等於所有的石頭總分 - 捨棄的石頭最低總分，看出這點之後用動態規畫解題。為了便於結算最後一顆石頭的狀態，可以在 $nums$ 最後面再加一個 $0$。開一個長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表在捨棄 $nums[i]$ 的狀況下，所有捨棄的石頭最低總分，有 $2$ 種狀況：

1. $i \leq k$，沒有更前面的石頭被捨棄，只要捨棄第 $i$ 顆石頭，$dp[i] = nums[i]$。
2. $i > k$，從第 $i-1-k$ 到 $i-1$ 顆石頭之中捨棄一顆，並且捨棄第 $i$ 顆石頭，$dp[i] = \min_{i-1-k \leq j \leq} dp[j] + nums[i]$。

如果在更新 $dp$ 時每次都要找 $dp[i-1-k]$ 到 $dp[i-1]$ 之間的最小值，這樣速度會太慢，可以利用滑動視窗及單調隊列加速。開一個雙向佇列 $que$，儲存寬度為 $k+1$ 的視窗範圍內 $dp$ 值最小的索引值，保持隊列為嚴格遞增，則視窗範圍內 $dp$ 最小值對應的索引值一定會在 $que$ 的最前面。更新 $que$ 時要依照以下的順序：

1. 移除 $que$ 前端已經出界的項目，也就是索引值小於 $i-1-k$ 的項目。
2. 更新 $dp$，如果 $i \leq k$ 則 $dp[i] = nums[i]$；反之，$dp[i] = nums[i] + dp[que[0]]$。
3. 移除 $que$ 後端大於、等於 $dp[i]$ 的項目。
4. $i$ 加入 $que$ 後端

Python 程式碼

解題時間約為 88 ms，使用記憶體約為 24.7 MB。

def solve():
    import sys
    from collections import deque
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield int(part)
    
    tokens = get_tokens()
    
    while True:
        try:
            n = next(tokens)
            k = next(tokens)
        except StopIteration:
            break
        
        nums = [next(tokens) for _ in range(n)] + [0]
        total = 0
        dp = [0] * (n+1)
        que = deque()
        for i in range(n+1):
            total += nums[i]
            # 移除前端出界的項目
            while que and que[0] < i-k-1:
                que.popleft()
            # 更新 dp[i]
            if i <= k:
                dp[i] = nums[i]
            else:
                dp[i] = nums[i] + dp[que[0]]
            # 移除後端較大的項目
            while que and dp[que[-1]] >= dp[i]:
                que.pop()
            # i 加入 que
            que.append(i)
        sys.stdout.write(f"{total - dp[-1]:d}\n")

if __name__ == "__main__":
    solve()

C++ 程式碼

解題時間約為 14 ms，使用記憶體約為 4.9 MB。

#include <cstdio>
#include <vector>
#include <deque>
typedef long long LL;
using namespace std;

int main() {
    int n, k;
    while(scanf("%d %d", &n, &k) != EOF) {
        vector<LL> nums (n+1, 0);
        for(int i = 0; i < n; i++) {
            scanf("%lld", &nums[i]);
        }
        LL total = 0;
        deque<int> que;
        que.push_back(0);
        vector<LL> dp (n+1, 0);
        for(int i = 0; i <= n; i++) {
            total += nums[i];
            // 移除前端出界的項目
            while(!que.empty() && que.front() < i-k-1) {
                que.pop_front();
            }
            // 更新 dp[i]
            if (i <= k) {
                dp[i] = nums[i];
            } else {
                dp[i] = nums[i] + dp[que.front()];
            }
            // 移除後端較大的項目
            while(!que.empty() && dp[que.back()] >= dp[i]) {
                que.pop_back();
            }
            // i 加入 que
            que.push_back(i);
        }
        
        printf("%lld\n", total - dp[n]);
    }
    return 0;
}