bzoj5311: 贞鱼

还是年轻啊算的时候少乘一个4000被卡二分上界了。。。%%%%bright教我超级快速读D飞bzoj垃圾卡常数据

我们容易写出这样的DP方程：f[i][j]=f[k][j-1]+val(k+1,j)

然后可以发现g(j)是单调减而且是下凸的

那么我们就可以愉快的上wqs二分了

那么f[i]就表示无限分最优解，就有f[i]=f[j]+val(j+1,i)+C

而这个明显是四边形不等式优化的形式

O(nlognlogw)踩了

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int MAXSIZE=<<;

char buf[MAXSIZE],*p1=buf,*p2=buf;

#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++

int read()

{

    int x=,f=;char ch=gc;

    while(ch<''||ch>''){if(ch=='-')f=-;ch=gc;}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=gc;}

    return x*f;

}

int n,s[][];

int val(int j,int i){return (s[i][i]-s[i][j]-s[j][i]+s[j][j])/;}

struct node

{

    int l,r,id;

    node(){}

    node(int L,int R,int ID){l=L;r=R;id=ID;}

}q[];int f[],g[];

void check(int C)

{

    int h=,t=;q[++t]=node(,n,);

    f[]=;g[]=;

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

    {

        if(q[h].r<i)h++;

        q[h].l=i;

        f[i]=f[q[h].id]+val(q[h].id,i)+C;

        g[i]=g[q[h].id]+;

        if(h>t||f[i]+val(i,n)<=f[q[t].id]+val(q[t].id,n))

        {

            while(h<=t&&f[i]+val(i,q[t].l)<=f[q[t].id]+val(q[t].id,q[t].l))t--;

            if(h>t)q[++t]=node(,n,i);

            else

            {

                int l=q[t].l,r=q[t].r,ans;

                while(l<=r)

                {

                    int mid=(l+r)/;

                    if(f[i]+val(i,mid)>f[q[t].id]+val(q[t].id,mid))

                    {

                        ans=mid;

                        l=mid+;

                    }

                    else r=mid-;

                }

                q[t].r=ans;

                q[++t]=node(ans+,n,i);

            }

        }

    }

}

int main()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    int K;

    n=read(),K=read();

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

        for(int j=;j<=n;j++)

        {

            s[i][j]=read();

            s[i][j]+=s[i-][j]+s[i][j-]-s[i-][j-];

        }

    int l=,r=(<<)-,ans;

    while(l<=r)

    {

        int mid=(l+r)/;

        check(mid);

        if(g[n]>=K)

        {

            ans=f[n]-K*mid;

            l=mid+;

        }

        else r=mid-;

    }

    printf("%d\n",ans);

    return ;

}