bzoj1010 玩具装箱toy

斜率优化dp第一题,纠结了n久。。最后输出改成%I64d就PE,要%lld才能ac,而且把输入也改成%lld比%I64d快看了200MS。。
终于大致清楚了斜率优化dp,记下几点:
(1)求最大值,维护上凸壳;求最小值,维护下凸壳;
(2)当点的横坐标单调,且斜率单调时,此时决策是单调的(即满足四边形不等式),可以用单调队列从前往后找最优决策(怎么找?只有最优决策点的值比两侧都要优,注意只有二字),找到之后前面的都是无用决策了,插入点的时候维护队列凸壳。
(3)如果点的横坐标是单调的,而斜率不单调,这时候决策是不单调的,但是可以发现最优决策点与两侧相邻点的斜率分别是k1,k2(k1 那么显然此时直线簇的斜率k满足k1 (4)当点的横坐标不单调且直线斜率不单调的时候。如果用单调队列,那么求最优决策点还是可以二分。当插入一个点的时候,我们首先根据它的横坐标二分出它的插入位置,然后维护凸壳,但是由于可能插入在队列中间,两边都要删点,复杂度过高。
正确做法是用平衡树维护动态凸壳。(我擦,说着简单,写着蛋疼无比)(这种情况细节还不太会,有待学习)

#include<stdio.h>
typedef long long ll;
const int maxn=5e4+10;
typedef struct Node{
    ll x,y;
}Node;
Node q[maxn];
int n;
ll s[maxn],L,dp[maxn];
int head,tail;
ll cal(ll x,ll y,ll k)
{
    return y-2*k*x;
}
bool xielv(Node a,Node b,Node c)
{
    ll x1=a.x,y1=a.y,x2=b.x,y2=b.y,x3=c.x,y3=c.y;
    return (y2-y1)*(x3-x2)<(y3-y2)*(x2-x1);
}
int main()
{
    int i,j;
    while(~scanf("%d%lld",&n,&L))
    {
        s[0]=0;dp[0]=0;
        ll tmp;
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&tmp);s[i]=s[i-1]+tmp;
        }
        head=tail=0;q[0].x=0;q[0].y=0;
        for(i=1;i<=n;i++)
        {
            ll k=s[i]+i-1-L,x,y;
            while(head<tail && cal(q[head].x,q[head].y,k)>=cal(q[head+1].x,q[head+1].y,k))
                head++;
            dp[i]=cal(q[head].x,q[head].y,k)+k*k;
            x=s[i]+i;y=dp[i]+x*x;
            Node tt;tt.x=x;tt.y=y;
            while(head<tail && !xielv(q[tail-1],q[tail],tt))
                tail--;
            q[++tail]=tt;
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>