首页 > ACM题库 > HDU-杭电 > HDU 3507-Print Article-动态规划-[解题报告]HOJ
2014
04-09

HDU 3507-Print Article-动态规划-[解题报告]HOJ

Print Article

问题描述 :

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
Monkey Party

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

输入:

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.

输出:

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.

样例输入:

5 5
5
9
5
7
5

样例输出:

230

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3507

题目大意:给定一个长度为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艹代码:

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


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

本文ZeroClock原创,但可以转载,因为我们是兄弟。

参考:http://blog.csdn.net/woshi250hua/article/details/7901433


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }