Hdu 3507 Print Article (DP_斜率优化)

题目大意：给定一个长度为n的序列，和一个常数m，我们可以将序列分成随意段，每段的权值为sum(arr[i]) + C(x<=i<=y)，求一种划分方法使得整个序列的权值最小.n<=50万。

解题思路：做完Hdu的2829，然后再看这题，一切变得如此简单，用两种方法解。
     状态转移方程为: dp[i] = min(dp[j] + (sum[i]-sum[j])^2 + m) (j < i);
     方法一：dp[i] = dp[j] + (sum[i]-sum[j])^2 + m = dp[j] + sum[i] * sum[i] + sum[j] * sum[j] - 2 * sum[i] * sum[j] + m;
     设y = dp[j] + sum[j] * sum[j],x = sum[j]，那么原式等于:dp[i] = y + 2 * sum[i] * x + m + sum[i] * sum[i],然后套下斜率优化DP模板即可ac。
     方法二:方法二使用的优化技巧类似于四边形不等式，用个s[i] 记录dp[i]由前面的哪个状态转移过来，然后枚举的时候只要枚举s[i-1] 到i-1就可以了。
     第二种方法似乎比第一种要慢一些，常数比较大。

测试数据：
Input
5 5
5 9 5 7 5
1 1000
1
3 1000
1 3 5
3 0
1 3 5
1 0
100000

OutPut:
230
1001
1081
35
10000000000

C艹代码：
[cpp]
#include <stdio.h>
#include <string.h>
#define MAX 510000
#define int64 long long

struct point{

    int64 x,y,c;
}pot[MAX];
int n,m,arr[MAX];
int64 sum[MAX],dp[MAX];
int qu[MAX],head,tail;

int CheckIt(int x,int y,int z) {

    point p0 = pot[x],p1 = pot[y],p2 = pot[z];
    return (p0.x -p1.x) * (p0.y - p2.y) - (p0.y - p1.y) * (p0.x - p2.x) <= 0;
}
int NotBest(int x,int y,int k) {

    point p0 = pot[x],p1 = pot[y];
    return p0.y - k * p0.x > p1.y - k * p1.x;
}
int64 Solve_DP() {

    head = tail = 0;
    qu[tail] = 0;
    pot[0].x = pot[0].y = 0;

    for (int i = 1; i <= n; ++i) {

        pot[i].x = sum[i-1];
        pot[i].y = dp[i-1] + sum[i-1] * sum[i-1];
        while (head <= tail - 1 &&
                CheckIt(qu[tail-1],qu[tail],i)) tail--;

        qu[++tail] = i;
        while (head + 1 <= tail &&
                NotBest(qu[head],qu[head+1],2 * sum[i])) head++;
        int k = qu[head];
        dp[i] = pot[k].y - 2 * sum[i] * pot[k].x + sum[i] * sum[i] + m;
    }

    return dp[n];
}
int64 Solve_DP2() {

    for (int64 mmin,i = 1; i <= n; ++i) {

        mmin = -1;
        for (int j = qu[i-1]; j < i; ++j)
            if (mmin == -1 ||
                    dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) < mmin) {

                mmin = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]);
                qu[i] = j;
            }

        dp[i] = mmin + m;
    }
    return dp[n];
}

int main()
{
    int i,j,k; www.zzzyk.com

    while (scanf("%d%d",&n,&m) != EOF) {

        for (i = 1; i <= n; ++i)
            scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];

        int64 ans = Solve_DP2();
        printf("%lld\n",ans);
    }
}

补充：软件开发 , C++ ,