Description：

有 $n$ 个人要坐 $k$ 辆车。如果第 $i$ 个人和第 $j$ 个人同坐一辆车，就会产生 $w_{i,j}$ 的代价。最小化代价。

$1\leqslant n\leqslant4000$

Solution：

转移方程是： $$ f[i][k]=\min(f[j][k-1]+val(j+1,i)) $$ 其中： $$ val(l,r)=\sum_{i=l}^r\sum_{j=l}^rw_{i,j} $$ 然后 $f[i][x]$ 单调减并且是下凸的，然后就可以 $WQS$ 二分了，不过我们会发现决策具有单调性，因为我们如果把 $val(l,r)$ 的区域画在二维平面上就会发现 $val(l,r)$ 满足四边形不等式，于是就可以决策单调性优化了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,k;

#define MAXN 4010

int s[MAXN][MAXN];

struct state

{

	int val,cnt;

};

inline state operator + (state a,state b){return (state){a.val + b.val,a.cnt + b.cnt};}

struct seg

{

	int l,r,p;

}q[MAXN];

int head,tail;

state f[MAXN];

inline int sum(int l,int r){return s[r][r] - s[r][l - 1] - s[l - 1][r] + s[l - 1][l - 1];}

inline bool operator < (state a,state b){return (a.val == b.val ? a.cnt < b.cnt : a.val < b.val);}

int val;

inline bool better(int a,int b,int p){return f[a] + (state){sum(a + 1,p) + val,1} < f[b] + (state){sum(b + 1,p) + val,1};}

inline state calc(int v)

{

	val = v;

	head = 1;tail = 0;

	f[0] = (state){0,0};

	q[++tail] = (seg){1,n,0};

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

	{

		f[i] = f[q[head].p] + (state){sum(q[head].p + 1,i) + val,1};

		++q[head].l;

		if(q[head].l > q[head].r)++head;

		register seg t;t.l = n + 1;t.r = n;t.p = i;

		while(head <= tail && better(t.p,q[tail].p,q[tail].l))t.l = q[tail--].l;

		if(head <= tail && better(t.p,q[tail].p,q[tail].r))

		{

			register int l = q[tail].l,r = q[tail].r,mid;

			while(l < r)

			{

				mid = ((l + r + 1) >> 1);

				if(better(q[tail].p,t.p,mid))l = mid;

				else r = mid - 1;

			}

			q[tail].r = l;t.l = l + 1;

		}

		if(t.l <= t.r)q[++tail] = t;

	}

	return f[n];

}

int main()

{

	scanf("%d%d",&n,&k);

	for(register int i = 1;i <= n;++i)for(register int j = 1;j <= n;++j)s[i][j] = rd();

	for(register int i = 1;i <= n;++i)for(register int j = 1;j <= n;++j)s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

	register int l = 0,r = 0x3f3f3f3f,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(calc(mid).cnt <= k)r = mid;

		else l = mid + 1;

	}

	cout << (calc(l).val - l * k) / 2 << endl;

	return 0;

}