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

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 ]
= 0, if i == j
= min{ dp[ i ][ k ] + dp[ k + 1 ][ j ] | Ɐ i ≤ k < j } + sum( i, j ), otherwise

http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=fcaa846ddcba22c1c63777723152ba9492a9f2218

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 )

"dp[ i ][ j ] 需要的決策點 k 必然落在 dp[ i ][ j - 1 ] 的決策點 k1 和 dp[ i + 1 ][ j ] 的決策點 k2 之間"

K[ i ][ j - 1 ] 和 K[ i + 1 ][ j ] 在 K[ i ][ j ] 之前被算出，我們發現前兩者的區間長度相同且皆小於後者

```#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;
}
```