HDU 4283 You Are the One：區間 DP 最小化總不滿意度

問題描述

n 人排隊上台表演，每人有一「屌絲值」 p_i。第 i 個上台者的不滿意度為 (i-1) * p_i。有一「黑屋子」（棧），每次可選隊首者直接上台，或進黑屋子。黑屋子中的人必須按進入順序反序出來（後進先出）。求調度順序使總不滿意度最小。

區間 DP 分析

考慮區間 [L, R] 內的人。第一個人 L 可以在第 k 位上台 (L ≤ k ≤ R)。則：

• [L+1, L+k-1] 這 k-1 人必須在 L 之前上台（他們進黑屋子，然後彈出）。
• [L+k, R] 這些人在 L 之後上台。

L 的不滿意度貢獻：(k-1) * p[L]。
後段 [L+k, R] 的人因 L 先上台，其上台序號整體 +1，額外不滿意度為 sum(L+k..R) * 1（即該段 p 值之和）。

狀態定義與轉移

• dp[L][R]：區間 [L, R] 內所有人上台的最小總不滿意度（假設他們是當前最先上台的連續區塊）。
• 轉移：dp[L][R] = min_{k=L..R} { dp[L+1][L+k-1] + (k-L)*p[L] + dp[L+k][R] + (sum[R]-sum[L+k-1])*(k-L+1-L?) }
  經整理：dp[L][R] = min_{i=L..R} { dp[L+1][i] + (i-L)*p[L] + dp[i+1][R] + (sum[R]-sum[i])*(i+1-L) }。

複雜度

• 狀態數 O(n^2)，轉移 O(n)，總時間 O(n^3)。n ≤ 100 可接受。
• 空間 O(n^2)。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, p[105], sum[105], dp[105][105];

int solve(int L, int R) {
    if (L >= R) return 0;
    if (dp[L][R] != -1) return dp[L][R];
    dp[L][R] = INF;
    for (int i = L; i <= R; ++i) {
        int cost = solve(L+1, i) + (i-L)*p[L] + solve(i+1, R) + (sum[R]-sum[i])*(i+1-L);
        dp[L][R] = min(dp[L][R], cost);
    }
    return dp[L][R];
}

int main() {
    int T; cin >> T;
    for (int cas=1; cas<=T; ++cas) {
        cin >> n;
        for (int i=1;i<=n;i++) { cin>>p[i]; sum[i]=sum[i-1]+p[i]; }
        memset(dp, -1, sizeof(dp));
        cout << "Case #" << cas << ": " << solve(1, n) << '\n';
    }
    return 0;
}