自动搬运

查看原文

来自洛谷，原作者为

	苏联小渣 believe in miracle.

搬运于2025-08-24 22:59:11，当前版本为作者最后更新于2024-06-13 19:53:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现 $n,k$ 都很小，考虑状压。

由于我们要求 $\max$ 之和，所以肯定要枚举这个 $\max$，也就是要钦定加入顺序，不难想到应该从大往小加入，这样每次加入的数都会成为一些区间的 $\max$。

设 $f_{S}$ 表示已经加入了最大的 $|S|$ 个数，且位置集合为 $S$ 的最小值。考虑枚举最后一个加入的数，位置不妨记为 $p$，考虑它会成为哪些区间的 $\max$。容易发现，这些区间应该包含 $p$ 且不包含更先加入的数。设二进制下 $S$ 中 $p$ 左边第一个 $1$ 的位置为 $l-1$，右边第一个 $1$ 的位置为 $r+1$，也就是所有满足 $l' \in [l,p],r' \in [p,r]$ 的 $[l',r']$ 的最大值都是 $k-|S|+1$。求出贡献区间数，本质上就是子矩形求和，可以通过二维前缀和预处理和查询，然后 dp 的转移也就简单了：

设贡献到的区间数为 $x$，那么 $f_S=\min \{f_{S-2^p}+x \times (k-|S|+1)\}$。于是总时间复杂度 $O(n2^n)$。

Code：

#include <bits/stdc++.h>
using namespace std;
int n, k, m, l, r, ans=1e9, pre[25][25], f[2000010], lst[25], nxt[25];
int main(){
	scanf ("%d%d%d", &n, &k, &m);
	for (int i=1; i<=m; i++){
		scanf ("%d%d", &l, &r);
		pre[l][r] ++;
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			pre[i][j] = pre[i][j] + pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1];
		}
	}
	for (int S=1; S<(1<<n); S++){
		int tot = 0;
		for (int i=0; i<n; i++){
			if ((S >> i) & 1) tot ++;
		}
		if (tot > k) continue;
		f[S] = 1e9, lst[0] = 0, nxt[n+1] = n+1;
		for (int i=0; i<n; i++){
			if ((S >> i) & 1) lst[i+1] = i+1;
			else lst[i+1] = lst[i];
		}
		for (int i=n-1; i>=0; i--){
			if ((S >> i) & 1) nxt[i+1] = i+1;
			else nxt[i+1] = nxt[i+2];
		}
		for (int i=0; i<n; i++){
			if (!((S >> i) & 1)) continue;
			int T = S - (1 << i);
			int st = lst[i], ed = nxt[i+2] - 2;
			int ad = pre[i+1][ed+1] - pre[st][ed+1] - pre[i+1][i] + pre[st][i];
			f[S] = min(f[S], f[T] + ad * (k - tot + 1));
		}
		if (tot == k) ans = min(ans, f[S]);
	}
	printf ("%d\n", ans);
	return 0;
}