HDOJ 2829 Lawrence（二维DP + 斜率优化）

题意：

有 n 个点，每个点有路与两侧点相连，要去掉一些路，使整个系统值最小。

思路：

1. 有 m 个炸药点，则可以转化为将线段分成 m + 1 段的情况来求解，dp[m][n] 表示到第 n 点为止，将 1~n 分成 m 段的最小值；

2. dp[k][i] = dp[k-1][j] + cost[j+1, i]; 如果枚举的话时间复杂度为 O(N² * M); 回到斜率优化，将代码优化到 O(N * M);

3. dp[k][i] = dp[k-1][j] + T[j] - S[i] * S[j] + S[i] * S[i] - T[i]; -> Y = dp[k-1][j] + T[j], X = S[j], a = S[i]（递增）;

4. 利用下凸函数的特性 + 队列对求 dp[k][i] 进行优化。本题还要克服的一个问题是关于初始化：dp[0][0] = 0, dp[0][else] = INFS;

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
const int INFS = 0x3fffffff;

int t1, t2, dp[2][MAXN], V[MAXN], S[MAXN], T[MAXN], deq[MAXN];

inline double slope(int i, int j)
{
    return 1.0 * (dp[t1][i] + T[i] - dp[t1][j] - T[j]) / (S[i] - S[j]);
}

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) && n && m)
    {
        V[0] = S[0] = T[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &V[i]);
            S[i] = S[i-1] + V[i];
            T[i] = T[i-1] + S[i] * V[i];
        }

        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i)
            dp[0][i] = INFS;

        t1 = 1, t2 = 0;
        for (int k = 1; k <= m + 1; ++k)
        {
            t1 ^= 1, t2 ^= 1;

            int s = 0, e = -1;
            for (int i = 0; i <= n; ++i)
            {
                while (s < e && slope(deq[s], deq[s+1]) <= S[i])
                    ++s;

                while (s < e && slope(deq[e], deq[e-1]) >= slope(i, deq[e]))
                    --e;
                deq[++e] = i;

                int j = deq[s];
                dp[t2][i] = dp[t1][j] + S[i] * (S[i] - S[j]) + T[j] - T[i];             
            }
        }
        
        printf("%d\n", dp[t2][n]);
    }
    return 0;
}