HDU 4283 You Are the One：區間動態規劃最小化不開心值

題目大意

n 位男生按 1..n 排隊，每人有「屌絲值」 D[i]。第 k 個上台者不開心值 = (k-1)*D[i]。導演可利用棧結構暗室（先進後出）暫存人員，改變上台順序。求最小總不開心值。

資料範圍：n ≤ 100, D[i] ≤ 100。

核心洞察：區間 DP 而非棧模擬

雖然暗室是棧，但直接模擬棧操作會導致狀態爆炸。關鍵觀察：最終上台順序是原序列的某種棧排列。區間 DP 直接建模最優決策。

狀態定義

dp[i][j]：處理區間 [i, j]（原序列連續段）的最小不開心總和。

轉移邏輯

考慮區間 [i, j] 中第一個上台的是第 k 個人（i ≤ k ≤ j）。則：

1. [i+1, k] 區間的人先上台（共 k-i 人），對應子問題 dp[i+1][k]。
2. 第 i 人第 k-i+1 個上台，不開心值 = D[i] * (k-i)。
3. [k+1, j] 區間的人後上台（排在第 k-i+2 位之後），整體不開心值增加 (sum[j]-sum[k]) * (k-i+1)（每人等待時間多 k-i+1），對應子問題 dp[k+1][j]。

綜合轉移：

dp[i][j] = min_{i≤k≤j} { dp[i+1][k] + dp[k+1][j] + D[i]*(k-i) + (sum[j]-sum[k])*(k-i+1) }

• sum[x] 為 D[1..x] 前綴和。
• 邊界：dp[i][i] = 0（單人無等待）。
• 按區間長度遞增 DP：len = 1..n-1，i = 1..n-len，j = i+len。

正確性論證

暗室棧操作等價於：對區間 [i,j]，選擇某個 k 作為「根」（第一個上台），左側 [i+1,k] 先遞歸處理（對應入棧後出棧），右側 [k+1,j] 後處理。此結構與二叉樹後序遍歷同構，完整覆蓋所有合法棧排列。

完整程式碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1 << 27;
const int MAXN = 105;
int a[MAXN], sum[MAXN], dp[MAXN][MAXN];

int main() {
    int T, n; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d", &n);
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
            for (int j = i+1; j <= n; j++)
                dp[i][j] = INF;
        for (int len = 1; len <= n-1; len++) {
            for (int i = 1; i <= n-len; i++) {
                int j = i + len;
                for (int k = i; k <= j; k++) {
                    dp[i][j] = min(dp[i][j],
                        dp[i+1][k] + dp[k+1][j] + a[i]*(k-i) + (sum[j]-sum[k])*(k-i+1));
                }
            }
        }
        printf("Case #%d: %d\n", cas, dp[1][n]);
    }
    return 0;
}

複雜度分析

• 狀態數 O(n^2)，轉移枚舉 O(n)，總時間 O(n^3) = 100^3 = 1e6，極快。
• 空間 O(n^2)。

關鍵細節

• dp[i+1][k] 當 k=i 時為 dp[i+1][i]（空區間），預設 0 正確。
• dp[k+1][j] 當 k=j 時為 dp[j+1][j]（空區間），預設 0 正確。
• 前綴和 sum 用 long long 亦可，但 n*maxD = 10000，int 足夠。