HDU 3507

布满荆棘的人生 2022-01-28 09:23 108阅读 0赞

## 题意：就是要输出N个数字a\[N\]，输出的时候可以连续连续的输出，每连续输出一串，它的费用是 “这串数字和的平方加上一个常数M”。 ##

## 分析：我们设dp\[i\]表示输出到i的时候最少的花费，sum\[i\]表示从a\[1\]到a\[i\]的数字和。于是方程就是：dp\[i\]=dp\[j\]+M+(sum\[i\]-sum\[j\])^2；很显然这个是一个二维的。题目的数字有500000个，不用试了，二维铁定超时了，需要使用斜率优化。 ##

## 参考： ##

## [https://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html][https_www.cnblogs.com_kuangbin_archive_2012_08_26_2657650.html] ##

## [https://www.bilibili.com/video/av23958626?from=search&seid=16700883105640588805][https_www.bilibili.com_video_av23958626_from_search_seid_16700883105640588805] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=500010;
    int dp[MAXN];
    int q[MAXN];//队列
    int sum[MAXN];
    
    int head,tail,n,m;
    // dp[i]= min{ dp[j]+M+(sum[i]-sum[j])^2 };
    int getDP(int i,int j)
    {
        return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);
    }
    
    int getUP(int j,int k) //yj-yk部分
    {
        return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]);
    }
    int getDOWN(int j,int  k)
    {
        return 2*(sum[j]-sum[k]);
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&m)==2)
        {
            for(int i=1;i<=n;i++)
               scanf("%d",&sum[i]);
            sum[0]=dp[0]=0;
            for(int i=1;i<=n;i++)
               sum[i]+=sum[i-1];
            head=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\n",dp[n]);
        }
        return 0;
    }

[https_www.cnblogs.com_kuangbin_archive_2012_08_26_2657650.html]: https://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html
[https_www.bilibili.com_video_av23958626_from_search_seid_16700883105640588805]: https://www.bilibili.com/video/av23958626?from=search&seid=16700883105640588805