设:

\(dp[i][j]\)表示前\(i\)辆车，装下\(j\)只的最小怨气值和。

\(sum[i][j]\)表示从把第\(i\)只到第\(j\)只放在同一辆车上的怨气值和。这里可以用“二维前缀和”的方式预处理然后\(O(1)\)查询。

则：\(dp[i][j]\) = min(dp[i−1][k]+sum[k+1][j]) \((i \le k \le j)\)
\(O(N^2\times K)\)暴力DP就出来了！

我们可以考虑将这过程进行优化。
先介绍什么是 决策 ：通俗来说就是DP方程最优从哪里转移过来，例如上面方程的\(k\)就是一个可以转移过来的地方，那么从某个\(k\)转移而来，DP值最小，则这个\(k\)就是此方程的决策。

把上述暴力DP打出DP的决策转移表来就可以发现这个DP方程决策是具有单调性的。
如果我们记前i只痞老板放在\(k\)辆车的决策为\(op[i][k]\)，我们就可以发现\(op[i-1][k] \le op[i][k]\)。

问题来了，知道决策是具有单调性的有什么用处呢？

对于上面的DP方程，我们枚举了所有可能成为决策的地方进行转移，若是知道决策是具有单调性的，那么就可以忽略许多可能成为决策的地方,进行快速转移，大大降低时间复杂度。根据上次DP值的决策，就可以知道下次DP值的决策在哪一段区间内，循环范围缩小。

怎么实现上述宏观思想呢？我们想到了：分治！

首先我们可以定义\(solve(l,r,L,R)\)表示当前在处理区间为\([l,r]\)，最优决策区间为\([L,R]\)。

设\(mid\)为\((l+r)/2\)，然后在递归每一层循环枚举L ~ min(R,mid−1)，记录最小DP值及其的决策\(where\)。然后更新。

递归至下一层，分两类： \(solve(l,mid-1,L,where)\) 与 \(solve(mid+1,r,where,R)\)这就充分体现了决策单调性的作用。

对于原始DP方程每次转移换成按照上述的过程进行的分治，外部循环\(K\)次即可。

具体实现可以参照下面代码。。。我使用了滚动数组。。。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 4010,inf = 2147483647;

int f[maxn],g[maxn],a[maxn][maxn];
int n,k;

inline int read()
{
    int ans = 0;char ch = getchar();
    while(ch<'0'||ch>'9')   ch = getchar();
    while(ch<='9'&&ch>='0') ans = ans*10+ch-'0',ch = getchar();
    return ans;
}

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

inline void init()
{
    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] - a[i-1][j-1] + read();
    for(int i=1;i<=n;i++)
        f[i] = calc(1,i);
}

void solve(int l,int r,int L,int R)
{
    if(l>r || L>R)  return;
    int mid = (l+r)>>1,value = inf,where;
    for(int i=L;i<=R && i < mid;++i)
    {
        int  p = g[i] + calc(i+1,mid);
        if(p<value)
        {
            value = p;
            where = i;
        }
    }
    f[mid] = min(f[mid],value);
    solve(l,mid-1,L,where);
    solve(mid+1,r,where,R);
}

int main()
{
    scanf("%d%d",&n,&k);
    init();
    for(int i=2;i<=k;i++)
    {
        memcpy(g,f,sizeof(f));
        memset(f,0x3f,sizeof(f));
        solve(i,n,i-1,n-1);
    }
    printf("%d\n",f[n]);
    return 0;
}