大胆猜想答案随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<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x; } struct FastIO { static const int S = 1e7; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if (pos == len) pos = 0, len = fread(buf, 1, S, stdin); if (pos == len) exit(0); return buf[pos++]; } inline int xuint() { int c = xchar(), x = 0; while (c <= 32) c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x; } inline int xint() { int s = 1, c = xchar(), x = 0; while (c <= 32) c = xchar(); if (c == '-') s = -1, c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline void xstring(char *s) { int c = xchar(); while (c <= 32) c = xchar(); for (; c > 32; c = xchar()) * s++ = c; *s = 0; } inline void wchar(int x) { if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos++] = x; } inline void wint(ll x) { if (x < 0) wchar('-'), x = -x; char s[24]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n--) wchar(s[n]); wchar(' '); } inline void wstring(const char *s) { while (*s) wchar(*s++); } ~FastIO() { if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } } 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-1][j]-a[j][i-1]+a[i-1][i-1]>>1;} bool isbetter(int x,int y,int i){return f[x]+calc(x+1,i)<f[y]+calc(y+1,i)||f[x]+calc(x+1,i)==f[y]+calc(y+1,i)&&g[x]<g[y];} pair<int,ll> check(int cost) { memset(f,42,sizeof(f));f[0]=0; stk[top=1]=0,L[1]=1,R[1]=n; for (int i=1;i<=n;i++) { int l=1,r=top,x; while (l<=r) { int mid=l+r>>1; if (R[mid]>=i) x=stk[mid],r=mid-1; else l=mid+1; } f[i]=f[x]+calc(x+1,i)+cost; g[i]=g[x]+1; while (L[top]>i&&isbetter(i,stk[top],L[top])) top--; l=i+1,r=R[top],x=R[top]+1; while (l<=r) { int mid=l+r>>1; if (isbetter(i,stk[top],mid)) x=mid,r=mid-1; else l=mid+1; } R[top]=x-1;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 "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=a[i-1][j]+a[i][j-1]+io.xint()-a[i-1][j-1]; int l=-100000000,r=-l,ans; while (l<=r) { int mid=l+r>>1; if (check(mid).first<=m) ans=mid,r=mid-1; else l=mid+1; } cout<<check(ans).second-1ll*m*ans; return 0; }