您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

Codeforces 505C：Mr. Kitayuta 尋寶記 — 動態規劃與狀態壓縮深度解析

編輯：關於C++

問題背景

30001 座島嶼排成一線，第 i 島有寶石。Kitayuta 從 0 號島出發，首跳長度為 d，之後每跳長度只能比上一跳減 1、不變、或加 1（且必須為正）。求能收集的最大寶石數。
輸入：n（寶石數）、d（首跳長度），隨後 n 行寶石位置 p_i（遞增）。
限制：n, d ≤ 30000，時間 1 秒，記憶體 256 MB。

朴素 DP 與瓶頸

定義 dp[i][j] 為跳到島 i、上一跳長度為 j 時的最大寶石數。狀態轉移：

dp[i][j] = gems[i] + max(
    dp[i+j][j],     // 同長度
    dp[i+j+1][j+1], // 加 1
    dp[i+j-1][j-1]  // 減 1，需 j>1
)

直接二維 DP 需 O(30000²) 時間空間，不可行。

關鍵觀察：跳躍長度範圍極小

證明：若總是取 l+1，跳躍長度從 d 遞增。前 245 次跳躍總和 d + (d+1) + ... + (d+245) ≥ 1+2+...+245 = 30135 > 30000，因此跳躍長度永不超過 d+245。同理，若總是取 l-1，長度不會低於 d-245（d≥247 時）。
結論：只需考慮 j ∈ [d-245, d+245]，共 491 個值。空間壓縮為 dp[30001][491]，複雜度降為 O(30000 × 491) ≈ 1.5×10⁷，輕鬆過線。

實現細節

用 offset = 250 映射跳躍長度到數組索引：idx = j - d + offset。
初始化 dp[d][offset] = gems[d]。
按島嶼編號從小到大轉移，同步更新答案。
用靜態數組而非 map，避免常數因子過大。

核心代碼（C++）

#include 
using namespace std;
const int M = 30001;
const int C = 250;
int n, d;
int gems[M] = {0};
int dp[M][2*C+1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> d;
    for (int i = 0, p; i < n; ++i) {
        cin >> p;
        ++gems[p];
    }
    memset(dp, -1, sizeof(dp));
    dp[d][C] = gems[d];
    int ans = gems[d];

    for (int i = d; i < M; ++i) {
        for (int j = 0; j <= 2*C; ++j) if (dp[i][j] >= 0) {
            int len = j - C + d; // 實際跳躍長度
            // 同長度
            if (len > 0 && i + len < M) {
                dp[i+len][j] = max(dp[i+len][j], dp[i][j] + gems[i+len]);
                ans = max(ans, dp[i+len][j]);
            }
            // 加 1
            if (i + len + 1 < M) {
                dp[i+len+1][j+1] = max(dp[i+len+1][j+1], dp[i][j] + gems[i+len+1]);
                ans = max(ans, dp[i+len+1][j+1]);
            }
            // 減 1
            if (len > 1 && i + len - 1 < M) {
                dp[i+len-1][j-1] = max(dp[i+len-1][j-1], dp[i][j] + gems[i+len-1]);
                ans = max(ans, dp[i+len-1][j-1]);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}