自动搬运

查看原文

来自洛谷，原作者为

	Zelotz **

搬运于2025-08-24 22:52:09，当前版本为作者最后更新于2025-07-18 10:50:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

观察：固定选择的区间后，如何使总代价最小？把所有区间按 $C$ 从大到小排序，按照这个顺序依次考虑它们会不会被选取。

这里我们说一个区间 $[L,R]$ 的权值就是满足 $L\leq l\leq r\leq R$ 且$(l,r)$ 被选取者中 $C(l,r)$ 最大值。

转化：于是先把所有区间从大到小排序，考虑 dp。

你发现此时我们只关心：第一，选取了多少个区间；第二，哪些 $[L,R]$ 的权值已经固定：当我们确定 $(l,r)$ 被选取后，所有满足 $L\leq l\leq r\leq R$ 且还未确定权值的 $[L,R]$ ，其权值就会确定。

设 $dp_{i,k,S}$ 是考虑了前 $i$ 个区间，当前选了 $k$ 个区间，已知权值者状态为 $S$ 时的最大总权值。

观察：发现，若 $[L,i]$ 权值已知， $[L,i+1]$ 权值一定也是已知的。如果我们令 $a_L$ 是最小的 $R$ 满足$[L,R]$ 权值已知，那可以发现一件容易说明的事情：$a$ 单调不降。

所有的 $a$ 状态与 $S$ 一一对应，于是 $S$ 可以看成是 $(0,0)$ 到 $(n,n)$ 的一条路径上方的格子形成的集合，可能的 $S$ 只有 $\dbinom{2n}{n}$ 种。

预处理出状态 $S$ 加入 $(l,r)$ 后变成了哪个状态。复杂度 $\mathcal O(n^4\dbinom{2n}n)$ 。也可以用 map。实际上我先写的 $\mathcal O(n^5\dbinom{2n}n\log n)$ 直接过了，甚至没跑到 1s。

#define int ll
const int N = 10, P = 998244353;
typedef __int128 LL;
int n, a[N];

map <LL, int> dp[N * N][N * N];
struct itv {
	int l, r, x;
	bool operator < (const itv &t) const {
		return x > t.x;
	}
} arr[N * N];
int sum[N];
signed main() {
	cin >> n;
	R(i, 1, n) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	int m = 0;
	R(i, 1, n) {
		int s = 0;
		R(j, i, n) {
			s += a[j];
			arr[++m] = {i, j, s};
		}
	}
	sort(arr + 1, arr + m + 1);
	
	dp[0][0][0] = 0;
	
	auto fill = [&](int i, int j, LL s, int val) {
		if (!dp[i][j].count(s)) {
			dp[i][j][s] = val;
		} else {
			dp[i][j][s] = max(dp[i][j][s], val);
		}
	} ;
	auto id = [&](int l, int r) {
		return (l - 1) * n + r;
	} ;
	LL all = 0; int alls = 0;
	R(l, 1, n) {
		R(r, l, n) {
			all |= (__int128(1) << id(l, r));
			alls += sum[r] - sum[l - 1];
		}
	}
	R(i, 0, m - 1) {
		R(j, 0, i) {
			for (auto [s, val] : dp[i][j]) {
				fill(i + 1, j, s, val);
				LL st = 0; int d = 0;
				R(l, 1, n) {
					R(r, l, n) {
						if (s >> id(l, r) & 1) {
							st |= (__int128(1ll) << id(l, r));
						} else if (l <= arr[i + 1].l && r >= arr[i + 1].r) {
							st |= (__int128(1ll) << id(l, r));
							d += sum[arr[i + 1].r] - sum[arr[i + 1].l - 1];
						}
					}
				}
//				assert((st & s) == s);
				fill(i + 1, j + 1, st, val + d);
			}
		}
	} 
	R(i, 1, m) {
		int mx = 0;
		for (auto [s, val] : dp[m][i]) {
			mx = max(mx, val);
		}
		cout << alls - mx << endl;
	}
	return 0;