HDU 2829 Lawrence[斜率優化dp]

題意：大概就是給你n(1<=n<=1000)個數，要你將其分成m + 1(0<=m<n)組，要求每組數必須是連續的而且要求得到的價值最小。一組數的價值定義為該組內任意兩個數乘積之和，如果某組中僅有一個數，那麼該組數的價值為0。如：
將“4 5 1 2”分成一組得到的價值為：4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49；
將“4 5 1 2”分成“4 5”和“1 2”兩組得到的價值為：4*5 + 1*2 = 22；
將“4 5 1 2”分成“4”和“5 1 2”兩組得到的價值為：0 + 5*1 + 5*2 + 1*2 = 17。

分析：本題可以用動態規劃來解決，但需要斜率優化。
定義dp[i][j]表示將前j個數分成i組所得到的價值，sum[i]表示前i個數之和，w[i]表示前i個數分成一組的價值，則：
dp[i][j] = min{dp[i-1][k] + val(k+1, j)} (i-1<=k<j)，val(k+1, j)為將第k+1~j個數分為一組的價值。對該式變形得：
dp[i][j] = min{dp[i-1][k] + w[j] - w[k] - sum[k]*(sum[j] - sum[k])}
          = min{dp[i-1][k] - w[k] + sum[k]*sum[k] - sum[k]*sum[j]} + w[j] (i-1<=k<j).
然後，就可以對該dp進行斜率優化。

[cpp]
#include <iostream> 
#include <cstring> 
#include <cstdio> 
#include <algorithm> 
#include <cmath> 
 
using namespace std; 
 
const int maxn = 1010; 
int n, m; 
int a[maxn], sum[maxn], w[maxn]; 
int dp[maxn][maxn]; 
int q[maxn], head, tail; 
 
int dy(int x, int j, int i) 
{ 
    return dp[x][i] - w[i] + sum[i] * sum[i] - (dp[x][j] - w[j] + sum[j] * sum[j]);  
} 
 
int dx(int j, int i) 
{ 
    return sum[i] - sum[j]; 
} 
 
void DP() 
{ 
    for (int i = 1; i <= n; ++i) { 
        dp[1][i] = w[i]; 
    } 
    for (int i = 2; i <= m + 1; ++i) { 
        head = tail = 0; 
        q[tail++] = i - 1; 
        for (int j = i; j <= n; ++j) { 
            while (tail - head >= 2) { 
                int p = q[head], k = q[head+1]; 
                if (dy(i - 1, p, k) < sum[j] * dx(p, k)) { 
                    head++; 
                } else { 
                    break; 
                }  
            } 
            dp[i][j] = dp[i-1][q[head]] + w[j] - w[q[head]] - sum[q[head]] * (sum[j] - sum[q[head]]); 
            while (tail - head >= 2) { 
                int p = q[tail-2], k = q[tail-1]; 
                if (dy(i - 1, p, k) * dx(k, j) >= dx(p, k) * dy(i - 1, k, j)) { 
                    tail--; 
                } else { 
                    break; 
                } 
            } 
            q[tail++] = j; 
        } 
    } 
    printf("%d\n", dp[m+1][n]);  
} 
 www.2cto.com
int main() 
{ 
    while (scanf("%d%d", &n, &m) != EOF) { 
        if (n == 0 && m == 0) break; 
        sum[0] = 0; 
        w[0] = 0; 
        for (int i = 1; i <= n; ++i) { 
            scanf("%d", &a[i]); 
            sum[i] = sum[i-1] + a[i]; 
            w[i] = w[i-1] + sum[i-1] * a[i];  
        } 
        DP(); 
    } 
    return 0; 
}