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