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

Sicily 1419 動態規劃深度解析：狀態壓縮與轉移優化

編輯：關於C++

在解決算法競賽題目時，動態規劃（DP）往往是突破難關的關鍵。Sicily 1419 這道題目便是一個典型的「看似常規，實則需要巧妙狀態定義」的動態規劃問題。本文將詳細拆解其解題思路、狀態定義、轉移方程以及最終的代碼實現。

題目回顧與初步想法

題目要求我們在給定條件下求解最短總時間。初見題目，直覺會定義 dp[i][j] 表示從第 i 個點到達第 j 個點的最短時間。然而，這種定義存在嚴重缺陷：推導下一個狀態時，需要依賴再上一個點的數據（因為送奶速度越慢花費時間越多），導致時間複雜度高達 O(n^3)，必然超時。

要解決這道題，必須攻克兩個核心問題：

如何搜遍所有數據可能性？
如何高效計算最終的總時間？

關鍵洞察：狀態的重新定義

經過深入思考，發現可以從「最優策略」的角度切入：

決策單一性：為了使總時間最小，經過某個點時必然會放下牛奶。假設當前送到了第 i+1 家，那麼第 i 家必然是從第 L 層上來的離 i+1 最近的一家，或者是另一頭的某一家。這意味著轉移來源並非 n 種情況，而是極其有限的幾種。
時間影響的累積性：當前的時間會對後續產生影響。若從當前點走到下一點距離為 d，剩餘 x 個點，則最後總時間增加 d * x。這一發現將問題簡化為區間動態規劃。

最終解法：區間 DP 雙端點狀態

首先將所有樓層（包括 L）排序。定義 dp[i][j] 為已處理區間 [i, j] 內所有點的最短時間。但僅此不夠，因為終點位置（在區間左端或右端）會影響後續擴展的代價，故需維護兩個 DP 陣列：

dp[0][i][j]：當前終點在區間左端（索引 i）的最小時間。
dp[1][i][j]：當前終點在區間右端（索引 j）的最小時間。

設 index 為 L 的索引，a[] 為排序後的樓層數組，n 為總點數。狀態轉移方程如下：

dp[0][i][j] = min(
    dp[0][i+1][j] + (a[i+1] - a[i]) * (n - j + i),
    dp[1][i+1][j] + (a[j] - a[i]) * (n - j + i)
);

dp[1][i][j] = min(
    dp[1][i][j-1] + (a[j] - a[j-1]) * (n - j + i),
    dp[0][i][j-1] + (a[j] - a[i]) * (n - j + i)
);

其中 (n - j + i) 代表當前尚未訪問的點數（即剩餘影響因子）。邊界條件為 dp[0][index][index] = dp[1][index][index] = 0。最終答案為 min(dp[0][0][n-1], dp[1][0][n-1])。

代碼實現（C++）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int n, L, a[1005], dp[2][1005][1005];

int main() {
    int T, index;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &L);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        a[n] = L;
        sort(a, a + n + 1); // 包含 L 共 n+1 個點
        // 找到 L 的索引
        for (index = 0; index <= n; index++) if (a[index] == L) break;

        memset(dp, 0x3f, sizeof(dp));
        dp[0][index][index] = dp[1][index][index] = 0;

        // 區間長度從 1 到 n+1
        for (int len = 2; len <= n + 1; len++) {
            for (int i = 0; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                if (i <= index && index <= j) { // 區間必須包含 L
                    int remain = n - (j - i); // 剩餘未訪問點數
                    if (i < index) {
                        dp[0][i][j] = min(
                            dp[0][i+1][j] + (a[i+1] - a[i]) * remain,
                            dp[1][i+1][j] + (a[j] - a[i]) * remain
                        );
                    }
                    if (j > index) {
                        dp[1][i][j] = min(
                            dp[1][i][j-1] + (a[j] - a[j-1]) * remain,
                            dp[0][i][j-1] + (a[j] - a[i]) * remain
                        );
                    }
                }
            }
        }
        printf("%d\n", min(dp[0][0][n], dp[1][0][n]));
    }
    return 0;
}