一眼可以看出$O(kn^{2})$的$dp$方程，然后就不会了呜呜呜。
设$f_{i, j}$表示已经选到了第$i + 1$个数并且选了$j$段的最小代价，那么
$f_{i, j} = f_{p, j - 1} + sum(p + 1, i) (0 \leq p \leq i)$
这个$sum$可以通过把&j > i&的格子的值记为$0$，预处理前缀和得到。
$sum(x, y) = s_{y, y} - s_{y, x}$
以下全都不是我想出来的：
外层枚举$j$可以划分阶段转移，不容易看出决策具有单调性。具体来说，假设当前要转移到$i$， 对于两个决策点$x$和$y$（假设$x < y$），如果有$f_{x} - s_{i, x} > f_{y} - s_{i, y}$，那么永远都不会用$x$去转移，我们可以在单调队列中二分来维护这个单调性，时间复杂度降至$O(knlogn)$，已经可以通过CF的数据了，但是BZOJ的变态时限是永远不可能把这个复杂度的程序放过去的。
考虑到把$n$个物品划分为$k$段，相当于强制选择$k$个，可以想到wqs二分。（感觉根本理解得不够啊喂喂），这样时间复杂度可以降至$O(n log n log sum)$，就可以AC了。
注意使用超级读优$IOread$。
虽然感觉是一道很好的题，但是考场上看到就等死吧。
Code：
#include <cstdio> using namespace std; const int N = 4005; int n, m, s[N][N], f[N], q[N], cnt[N]; namespace IOread{ const int L = 1<<15; char buffer[L],*S,*T; inline char Getchar() { if(S == T) { T = (S = buffer) + fread(buffer, 1, L, stdin); if(S == T) return EOF; } return *S++; } template <class T> inline void read(T &X) { char ch; T op = 1; for(ch = Getchar(); ch > ‘9‘ || ch < ‘0‘; ch = Getchar()) if(ch == ‘-‘) op = -1; for(X = 0; ch >= ‘0‘ && ch <= ‘9‘; ch = Getchar()) X = (X << 1) + (X << 3) + ch - ‘0‘; X *= op; } } using namespace IOread; inline int query(int x, int y) { return s[y][y] - s[y][x]; } inline int calc(int x, int y) { int ln = y + 1, rn = n, mid, res = n + 1; for(; ln <= rn; ) { mid = (ln + rn) / 2; int v1 = f[x] + query(x, mid), v2 = f[y] + query(y, mid); if(v1 > v2 || (v1 == v2 && cnt[x] > cnt[y])) res = mid, rn = mid - 1; else ln = mid + 1; } return res; } inline bool chk(int mid) { int l = 1, r = 1; q[1] = 0; for(int i = 1; i <= n; i++) { for(; l < r && calc(q[l], q[l + 1]) <= i; ++l); f[i] = f[q[l]] + query(q[l], i) + mid; cnt[i] = cnt[q[l]] + 1; for(; l < r && calc(q[r - 1], q[r]) > calc(q[r], i); --r); q[++r] = i; } return cnt[n] <= m; } int main() { read(n), read(m); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { read(s[i][j]); if(j > i) s[i][j] = 0; } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; int ln = 0, rn = s[n][n], mid, res = 0; for(; ln <= rn; ) { mid = (ln + rn) / 2; if(chk(mid)) rn = mid - 1, res = f[n] - mid * m; else ln = mid + 1; } printf("%d\n", res); return 0; }
CF321E Ciel and Gondolas & BZOJ 5311 贞鱼
原文：https://www.cnblogs.com/CzxingcHen/p/9542598.html
