HDU3507 Print Article —— 斜率优化DP

题目链接：https://vjudge.net/problem/HDU-3507

Print Article

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 14899    Accepted Submission(s): 4648

Problem Description

Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost

M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

 

Input

There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

 

Output

A single number, meaning the mininum cost to print the article.

 

Sample Input

5 5 5 9 5 7 5

 

Sample Output

230

 

Author

Xnozero

 

Source

2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT

 

Recommend

zhengfeng

题意：

给出一段字符串，每个位置上的字符都有其相应的价值Ci。将字符串分成若干子串，且每个子串的价值为sigma(Ci)^2+M，i的范围为区间的范围。问怎样分割能得到最小的价值？

题解：

动态规划问题，设dp[i]为前i个字符的最小价值。再设sum[i]为前i个字符的价值前缀和。

可得：dp[i] = min( dp[j] + (sum[i]-sum[j])^2 + M ) ) ， 其中 0<=k<=i-1。

整理：dp[i] = min( dp[j] + sum[i]^2 + sum[j]^2 - 2*sum[i]*sum[j] + M )， 其中 0<=j<=i-1。

最直接的做法是枚举j，求得最小值。但是此题n的范围为5e5，O（n^2）肯定超时了，所以要借用斜率优化，其方法是尽量排除掉那些不可能取得最优值的点，缩小状态转移的范围。推理如下：

1.如果 k<j，假设dp[i]在j处取得的值比k处取得的值要小，即更优，那么就有：

dp[j] + sum[i]^2 + sum[j]^2 - 2*sum[i]*sum[j] + M < dp[k] + sum[i]^2 + sum[k]^2 - 2*sum[i]*sum[k] + M，

整理得：[ (dp[j] + sum[j]^2) - (dp[k] + sum[k]^2) ] / ( 2*sum[j] - 2*sum[k] ) < sum[i]。

观察等式右边，可以看出这是一个斜率表达式。

我们设 yj = dp[j] + sum[j]^2， xj = 2*sum[j] ，那么上式就变为：( yj - yk ) / ( xj - xk ) < sum[i] 。

可知 ( yj - yk ) / ( xj - xk ) 就是直线 j---k 的斜率g[j,k]。

所以：当k<j，且j比k更优时， g[j,k] < sum[i]。而且，因为sum[i]递增，所以j比k更优的结论，对于i以后的位置也合适。……结论1（此结论用于求出dp[i]的最优转移状态）

2.当k<j<i时， 如果g[i,j] <= g[j,k]时， j可以直接排除。 ………………结论2（此结论用于维护队列）

1) 当g[i,j] < sum[i]时， i比j更优， 所以排除j。

2) 当g[i,j] >= sum[i] 时， g[j, k] >= sum[i]，表明k比j更优，所以排除j。

3.综上：只需维护一个队列，其两个相邻元素间所形成直线的斜率单调递增。

注意：

判断不等式的时候，由于避免整除除法的问题，把除法判断改成了乘法判断，但是要特别注意，移项是否为负数，如果为负数，那么不等式的方向就会发生变化。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int MAXM = 1e5+10;
const int MAXN = 5e5+10;

int dp[MAXN], sum[MAXN];
int q[MAXN];
int n, M;

int getUp(int i, int j)
{
    return (dp[i]+sum[i]*sum[i]) - (dp[j]+sum[j]*sum[j]);
}

int getDown(int i, int j)
{
    return 2*(sum[i]-sum[j]);
}

int getDp(int i, int j)
{
    return dp[i] = dp[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + M;
}

int main()
{
    while(scanf("%d%d", &n, &M)!=EOF)
    {
        sum[0] = 0;
        for(int i = 1; i<=n; i++)
            scanf("%d", &sum[i]), sum[i] += sum[i-1];

        dp[0] = 0;
        int head = 0, tail = 0;
        q[tail++] = 0;
        for(int i = 1; i<=n; i++)
        {
            //以下为寻找最优的转移状态。由于除法改成了乘法，所以顺序不能任意，否则不等号方向会改变。
            while(head+1<tail && getUp(q[head+1], q[head])<sum[i]*getDown(q[head+1], q[head])) head++;
            dp[i] = getDp(i, q[head]);
            //以下为维护队列
            while(head+1<tail && getUp(i, q[tail-1])*getDown(q[tail-1], q[tail-2])<=
                  getUp(q[tail-1], q[tail-2])*getDown(i, q[tail-1]) ) tail--;
            q[tail++] = i;
        }

        printf("%d
", dp[n]);
    }
}