BZOJ5311 贞鱼（动态规划+wqs二分+决策单调性）

　　大胆猜想答案随k变化是凸函数，且有决策单调性即可。去粘了份fread快读板子才过。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 4010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=;char c=getchar();

    while (c<''||c>'') c=getchar();

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x;

}

struct FastIO {

    static const int S = 1e7;

    int wpos;

    char wbuf[S];

    FastIO() : wpos() {}

    inline int xchar() {

        static char buf[S];

        static int len = , pos = ;

        if (pos == len)

            pos = , len = fread(buf, , S, stdin);

        if (pos == len) exit();

        return buf[pos++];

    }

    inline int xuint() {

        int c = xchar(), x = ;

        while (c <= ) c = xchar();

        for (; '' <= c && c <= ''; c = xchar()) x = x *  + c - '';

        return x;

    }

    inline int xint()

    {

        int s = , c = xchar(), x = ;

        while (c <= ) c = xchar();

        if (c == '-') s = -, c = xchar();

        for (; '' <= c && c <= ''; c = xchar()) x = x *  + c - '';

        return x * s;

    }

    inline void xstring(char *s)

    {

        int c = xchar();

        while (c <= ) c = xchar();

        for (; c > ; c = xchar()) * s++ = c;

        *s = ;

    }

    inline void wchar(int x)

    {

        if (wpos == S) fwrite(wbuf, , S, stdout), wpos = ;

        wbuf[wpos++] = x;

    }

    inline void wint(ll x)

    {

        if (x < ) wchar('-'), x = -x;

        char s[];

        int n = ;

        while (x || !n) s[n++] = '' + x % , x /= ;

        while (n--) wchar(s[n]);

        wchar('\n');

    }

    inline void wstring(const char *s)

    {

        while (*s) wchar(*s++);

    }

    ~FastIO()

    {

        if (wpos) fwrite(wbuf, , wpos, stdout), wpos = ;

    }

} io;

int n,m,a[N][N],g[N],stk[N],L[N],R[N],top;

ll f[N];

int calc(int i,int j){return a[j][j]-a[i-][j]-a[j][i-]+a[i-][i-]>>;}

bool isbetter(int x,int y,int i){return f[x]+calc(x+,i)<f[y]+calc(y+,i)||f[x]+calc(x+,i)==f[y]+calc(y+,i)&&g[x]<g[y];}

pair<int,ll> check(int cost)

{

    memset(f,,sizeof(f));f[]=;

    stk[top=]=,L[]=,R[]=n;

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

    {

        int l=,r=top,x;

        while (l<=r)

        {

            int mid=l+r>>;

            if (R[mid]>=i) x=stk[mid],r=mid-;

            else l=mid+;

        }

        f[i]=f[x]+calc(x+,i)+cost;

        g[i]=g[x]+;

        while (L[top]>i&&isbetter(i,stk[top],L[top])) top--;

        l=i+,r=R[top],x=R[top]+;

        while (l<=r)

        {

            int mid=l+r>>;

            if (isbetter(i,stk[top],mid)) x=mid,r=mid-;

            else l=mid+;

        }

        R[top]=x-;if (x<=n) stk[++top]=i,L[top]=x,R[top]=n;

    }

    return make_pair(g[n],f[n]);

}

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

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

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

        a[i][j]=a[i-][j]+a[i][j-]+io.xint()-a[i-][j-];

    int l=-,r=-l,ans;

    while (l<=r)

    {

        int mid=l+r>>;

        if (check(mid).first<=m) ans=mid,r=mid-;

        else l=mid+;

    }

    cout<<check(ans).second-1ll*m*ans;

    return ;

}