题目链接
题解
题意：将(n)个人分成(K)段，每段的人两两之间产生代价，求最小代价和
容易设(f[k][i])表示前(i)个人分成(k)段的最小代价和
设(val(i,j))为(i)到(j)两两之间产生的代价和，容易发现就是一个矩形，可以预处理前缀和(O(1))计算
那么有
[f[k][i] = min{f[k - 1][j] + val(j + 1,i)}
]
直接转移显然(O(n^2k))
我们把(val(j + 1,i))拆开，也不能分离(i)和(j)
很好，可以大胆猜想这个(dp)是符合决策单调性的
证明：
如果对于(x > y)且(x)作为(i)的决策，一定有
[f[k - 1][x] + val(x + 1,i) le f[k - 1][y] + val(y + 1,i)
]
那么对于(i' > i)，由几何面积可以得知(val(x + 1,i') - val(x + 1,i) le val(y + 1,i') - val(y + 1,i))
所以仍有
[f[k - 1][x] + val(x + 1,i') le f[k - 1][y] + val(y + 1,i')
]
故对于(i)决策时比(y)更优的(x)，在(i' > i)的决策时依旧更优
即该(dp)满足决策单调性
证毕
所以用一个队列维护三元组，即可做到(O(n^2 + knlogn))
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define REP(i,n) for (register int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 4005,maxm = 805,INF = 0x3f3f3f3f;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
struct tri{int l,r,pos;}q[maxn];
int head,tail;
int s[maxn][maxn],f[maxm][maxn],n,K,now;
inline int val(int i,int j){
return s[i][i] - s[i][j - 1] - s[j - 1][i] + s[j - 1][j - 1];
}
inline bool check(int pos,int i,int j){
return f[now - 1][i] + val(pos,i + 1) <= f[now - 1][j] + val(pos,j + 1);
}
inline void work(){
f[now][0] = INF;
q[head = tail = 0] = (tri){1,n,0};
tri u;
for (register int i = 1; i <= n; i++){
u = q[head];
f[now][i] = f[now - 1][u.pos] + val(i,u.pos + 1);
q[head].l++;
if (q[head].l > q[head].r) head++;
while (head <= tail){
u = q[tail--];
if (check(u.l,i,u.pos)){
if (head > tail) {q[++tail] = (tri){u.l,n,i}; break;}
continue;
}
else if (!check(u.r,i,u.pos)){
q[++tail] = u;
if (u.r == n) break;
q[++tail] = (tri){u.r + 1,n,i};
break;
}
else {
int l = i + 1,r = n,mid;
while (l < r){
mid = l + r >> 1;
if (check(mid,i,u.pos)) r = mid;
else l = mid + 1;
}
q[++tail] = (tri){u.l,l - 1,u.pos};
q[++tail] = (tri){l,n,i};
break;
}
}
}
}
int main(){
n = read(); K = read();
REP(i,n) REP(j,n) s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + read();
REP(i,n) f[1][i] = val(i,1); f[1][0] = INF;
for (now = 2; now <= K; now++) work();
printf("%d
",f[K][n] >> 1);
return 0;
}