自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:49:04，当前版本为作者最后更新于2021-12-13 16:58:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

*P3446 [POI2006]EST-Aesthetic Text

POI 合集。

还算有趣的动态规划。遇到这种区间划分题首先考虑 DP，设 $f_{i,j}$ 表示以第 $i$ 个单词结尾为一行，且这一行长度为 $j$ 的最小答案，那么有 $f_{i,j}=\min_{\\k=1}^m(f_{p,k}+|j-k|)$，其中 $p$ 满足 $i-p-1+\sum_{\\q=p+1}^i l_q=j$。直接转移的复杂度为 $\mathcal{O}(n^2m)$（枚举 $p$ 算出对应的 $j$）。

不过我们注意到有很多 $j$ 都是空值，说明这个定义有些劣。不妨修改定义，设 $f_{i,j}$ 表示最后一行为 $i-j+1\sim i$ 的答案，再设 $L_{i,j}$ 表示 $j-1+\sum_{\\p\in [i-j+1,i]}l_p$ 即 $i-j+1\sim i$ 组成一行的长度，那么有：

$$f_{i,j}=\min_{p\in[1,i-j]}(f_{i-j,p}+|L_{i-j,p}-L_{i,j}|) $$

此时时间复杂度优化为 $\mathcal{O}(n^3)$，但仍无法接受。接下来使用拆绝对值的技巧，即维护 $pre_{i,j}$ 表示 $f_{i,j}-L_{i,j}$，$suf_{i,j}$ 表示 $f_{i,j}+L_{i,j}$，那么对于 $f_{i,j}$ 对应的转移位置 $i-j$，我们只需找到最后一个位置 $p$ 使得 $L_{i-j,p}\leq L_{i,j}$，那么 $f_{i,j}$ 可以由 $pre_{i,p}$ 关于 $p$ 的前缀 $\min$ 加上 $L_{i,j}$，以及 $suf_{i,p+1}$ 关于 $p$ 的后缀 $\min$ 减去 $L_{i,j}$ 得到。

又因为固定 $i-j$ 时，$L_{i,j}$ 随着 $i$ 增大而增大，这说明 $f_{i+k,j+k}$ 从 $i-j$ 处转移时的 $p$ 随着 $k$ 增加而递增，因此对每个位置 $i$ 在求出 $f_{i,j}$ 维护一个转移指针即可做到平方。

const int N = 2e3 + 5;
int n, m, ans = 2e9, L[N], pos[N], tot[N], f[N][N];
int len[N][N], pre[N][N], suf[N][N];
int main(){
	cin >> m >> n;
	for(int i = 1; i <= n; i++) {
		cin >> L[i], L[i] += L[i - 1];
		for(int j = i - 1; ~j; j--) {
			int cur = i - j - 1 + L[i] - L[j];
			if(cur > m) break; tot[i]++;
			if(!j) f[i][tot[i]] = 0;
			else {
				f[i][tot[i]] = 2e9;
				while(pos[j] < tot[j] && len[j][pos[j] + 1] <= cur) pos[j]++;
				if(pos[j]) cmin(f[i][tot[i]], pre[j][pos[j]] + cur);
				if(pos[j] < tot[j]) cmin(f[i][tot[i]], suf[j][pos[j] + 1] - cur);
			} len[i][tot[i]] = cur;
		} pre[i][0] = suf[i][tot[i] + 1] = 2e9;
		for(int j = 1; j <= tot[i]; j++) pre[i][j] = min(pre[i][j - 1], f[i][j] - len[i][j]);
		for(int j = tot[i]; j; j--) suf[i][j] = min(suf[i][j + 1], f[i][j] + len[i][j]);
		if(i == n) for(int j = 1; j <= tot[n]; j++) cmin(ans, f[i][j]);
	} cout << ans << endl;
	return 0;
}