POJ 3661 Running：動態規劃狀態機模型

題目大意

奶牛跑步 n 分鐘，疲勞度上限 m。每分鐘可選跑或休息：

• 跑：疲勞度 +1，跑 v[i] 米。
• 休息：疲勞度每分鐘 -1，必須連續休息到疲勞度歸零。

求 n 分鐘後疲勞度為 0 時的最大跑步距離。n ≤ 10000, m ≤ 500。

DP 狀態定義

dp[i][j]：前 i 分鐘，當前疲勞度為 j 的最大距離。j=0 表示未疲勞或剛休息完。

轉移方程

• 跑：若 j < m，dp[i][j+1] = max(dp[i][j+1], dp[i-1][j] + v[i])。
• 休息：若 j > 0，休息會連續 j 分鐘直到疲勞度歸零，即從狀態 (i-1, j) 直接轉移到 (i+j-1, 0)： dp[i+j-1][0] = max(dp[i+j-1][0], dp[i-1][j])。
• 另外 j=0 時可保持休息：dp[i][0] = max(dp[i][0], dp[i-1][0])。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
const int MAXM = 505;

int dp[MAXN][MAXM];
int v[MAXN];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j > 0 && i + j - 1 <= n)
                    dp[i+j-1][0] = max(dp[i+j-1][0], dp[i-1][j]);
                else
                    dp[i][0] = max(dp[i][0], dp[i-1][0]);
                if (j < m)
                    dp[i][j+1] = max(dp[i][j+1], dp[i-1][j] + v[i]);
            }
        }
        printf("%d\n", dp[n][0]);
    }
    return 0;
}

關鍵點總結

• 休息操作是「跳躍式」轉移：直接跳到疲勞度歸零的那一分鐘，中間不產生距離。
• 需判斷 i+j-1 <= n 避免越界。
• 初始 dp[0][0]=0，其餘 0（距離非負）。
• 時間 O(n*m) ≈ 5e6，空間 O(n*m) 可滾動優化至 O(m)。

總結

POJ 3661 是狀態機 DP 經典題：疲勞度作為狀態，跑/休息對應不同轉移。休息的強制連續性導致跳躍轉移，需仔細處理邊界。代碼簡潔，是二維 DP 狀態機的優秀範例。