POJ 3186 Treats for the Cows：區間 DP 逆序推導

題目大意

有 n 顆糖果排成一行，價值 v[1..n]。每天從兩端取一顆賣出，第 i 天賣出的糖果收益 = 價值 × i。求最大總收益。n ≤ 2000。

區間 DP 狀態定義

dp[i][j]：剩下區間 [i, j] 時，將這些糖果全部賣完能獲得的最大收益。注意：這是「從後往前」的視角，即當前已賣出 n - (j-i+1) 天，下一顆賣出是第 (n - (j-i+1) + 1) 天。

轉移方程（逆序推導）

設當前區間長度 len = j-i+1，當前天數 day = n - len + 1。

dp[i][j] = max(
    dp[i+1][j] + v[i] * day,  // 取左端
    dp[i][j-1] + v[j] * day   // 取右端
)

初始條件：dp[i][i] = v[i] * n（最後一天賣最後一顆）。

按區間長度 len 從 2 到 n 遞增枚舉，保證轉移所需狀態已計算。

完整代碼

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 2005;
int v[MAXN];
int dp[MAXN][MAXN];

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
    for (int i = 1; i <= n; i++) dp[i][i] = v[i] * n;
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            int day = n - len + 1;
            dp[i][j] = max(dp[i+1][j] + v[i] * day,
                           dp[i][j-1] + v[j] * day);
        }
    }
    printf("%d\n", dp[1][n]);
    return 0;
}

關鍵點總結

• 區間 DP 典型技巧：逆序思考，從「剩下區間」狀態出發，向「更大區間」轉移。
• 按區間長度枚舉保證無後效性。
• 時間 O(n²)，空間 O(n²)，n=2000 約 400 萬狀態，可優化為兩行滾動數組 O(n) 空間（但需注意轉移順序）。
• 本題是區間 DP 入門經典例題。

總結

POJ 3186 展示了區間 DP 的核心思想：將「前向決策」轉化為「後向狀態」，通過區間長度枚舉實現無後效性轉移。掌握此模板可解決大類區間優化問題（如石子合併、戳氣球等）。