0w1

Monotonic optimal split point DP ( 凸性 2D / 1D 優化 )

DP Monotonous TOJ

http://sprout.tw/oj/pro/144/
Short summary for the problem: given an array of N ≤ 1000 numbers a[ 1 ], a[ 2 ] .., a[ N ], each pair of numbers a[ i ], a[ i + 1 ]adjacent to each other can merge into a new single number, producing a[ i ] + a[ i + 1 ] points, answer the minimum sum of points possible to produce after merging the whole array together.
DP 的漸進式很容易寫出來:
令 dp[ i ][ j ]: 把整個區間[ i, j ]融合後得到的分數總和則有
dp[ i ][ j ]
= 0, if i == j
= min{ dp[ i ][ k ] + dp[ k + 1 ][ j ] | Ɐ i ≤ k < j } + sum( i, j ), otherwise
很直觀的看法就是我們要找到一個適合的切割點使得 左右兩側獨立的dp值最大
如果我們直接照著定義做，會得到一個 狀態2D / 轉移1D 的時間複雜度，負荷不了測資的 N ≤ 1000
我們想，狀態很明顯不能再更低，所以如果這個算法能更好，就代表這樣盲目地枚舉k 是會考慮到許多不必要的狀態。查了一下網路，發現這個題目符合四邊形不等式優化的條件，根據
http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=fcaa846ddcba22c1c63777723152ba9492a9f2218
的最後一頁的證明，我們得到結論，若dp 要求的是:
dp[ i ][ j ] = min{ dp[ i ][ k ] + dp[ k + 1 ][ j ] | Ɐ i ≤ k < j } + w( i, j ), 且有邊界 dp[ i ][ i ] = 0,
還附帶這樣的不等式關係:
dp[ i ][ j ] + dp[ i + 1 ][ j + 1 ] ≥ dp[ i ][ j + 1 ] + dp[ i + 1 ][ j ], ( a.k.a. convex monge condition )
或者 w( i - 1, i + 1 ) ≥ max( w( i - 1, i ), w( i, i + 1 ) ), ( 其實和上面是等價的 )
一種比較直觀的看法是若且唯若區間長度向左向右增加，代價函數非嚴格遞增
則它有 "Optimal Split Point Monotonicity" 性質，
"dp[ i ][ j ] 需要的決策點 k 必然落在 dp[ i ][ j - 1 ] 的決策點 k1 和 dp[ i + 1 ][ j ] 的決策點 k2 之間"
如此的話，轉移的複雜度就能達到均攤O( 1 )，得到總複雜度O( n ^ 2 )，大幅的進步了。
所以我們現在令 K[ i ][ j ] 為 dp[ i ][ j ] 的最佳決策點 k, 我們會發現我們需要用某種方式枚舉，使得
K[ i ][ j - 1 ] 和 K[ i + 1 ][ j ] 在 K[ i ][ j ] 之前被算出，我們發現前兩者的區間長度相同且皆小於後者
所以我們依據區間的長度為主軸，利用這種優化一面維護最佳決策點，一面更新dp值

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 1e3 + 3;

int n;
int a[MAXN];
int pa[MAXN]; // prefix sum for a
int dp[MAXN][MAXN];
int K[MAXN][MAXN]; // 最佳決策點

void init(){
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            dp[i][j] = INF;
    for(int i = 1; i <= n; ++i){
        dp[i][i] = 0;
        K[i][i] = i;
    }
    for(int i = 1; i <= n; ++i)
        pa[i] = pa[i - 1] + a[i];
}

void solve(){
    for(int len = 2; len <= n; ++len) // 長度由小到大更新dp表
        for(int i = 1; i + len - 1 <= n; ++i){
            int j = i + len - 1; // [ i, j ] == [ i, i + len - 1 ]
            for(int k = K[ i ][ j - 1 ]; k <= K[ i + 1 ][ j ]; ++k) // 根據四邊形不等式優化的結論
                if( dp[i][j] > dp[ i ][ k ] + dp[ k + 1 ][ j ] ){ // 這個切割點更好
                    dp[i][j] = dp[ i ][ k ] + dp[ k + 1 ][ j ];
                    K[i][j] = k;
                }
            dp[i][j] += pa[j] - pa[i - 1]; // sum( i, j )
        }
    printf("%d\n", dp[1][n]);
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        init();
        solve();
    }
    return 0;
}