POJ 3186 區間 DP：從雙端取數最大化加權和

題目大意

給定長度 n 的數列 a[1..n]。每次從**左端**或**右端**取一個數，第 i 次取出的數乘以 i 計入總分。求最大總分。

狀態定義

dp[i][j]：已取 i 個數，其中從**左側**取了 j 個（右側取 i-j 個）的最大分數。
當前左端索引 = j+1，右端索引 = n - (i-j) + 1 = n - i + j + 1。

轉移方程

• 從左端取：dp[i][j] = dp[i-1][j-1] + a[j] * i （需 j > 0）
• 從右端取：dp[i][j] = dp[i-1][j] + a[n-i+j+1] * i
• 取兩者最大值。

邊界與答案

• dp[0][0] = 0。
• 最終答案 = max_{0≤j≤n} dp[n][j]。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2010;
int a[MAXN];
int dp[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                int val = 0;
                if (j > 0) val = max(val, dp[i-1][j-1] + a[j] * i);
                val = max(val, dp[i-1][j] + a[n - i + j + 1] * i);
                dp[i][j] = val;
            }
        }
        int ans = 0;
        for (int j = 0; j <= n; ++j) ans = max(ans, dp[n][j]);
        cout << ans << "\n";
    }
    return 0;
}

複雜度與優化

• 時間 O(n²)，空間 O(n²)（n ≤ 2000 約 16 MB）。
• 可滾動數組優化至 O(n) 空間，但非必要。
• 注意數組下標 1-based，右端索引推導：n - (i-j) + 1 = n - i + j + 1。