题解

把时间轴离散化

任意两个活动只要时间上有重叠，就必须被分配到同一场嘉年华，否则会违反“不同时举办”的限制。因此可以把所有起止时间加入数组并离散化，得到最多 $2n$ 个关键点。记 cnt[l][r] 为所有完全落在区间 $[l,r]$ 内的活动个数，显然若我们把整段时间交给某一场嘉年华，那么它能够接纳的活动数就是 cnt[l][r]。

前缀 DP：没有强制活动

按照离散化后的坐标顺序考虑前缀 $[1,i]$，设 dp_pf[i][s] 为“在前缀内恰好让第一场嘉年华接待 $s$ 个活动，第二场能够得到的最多活动数”。状态转移枚举最后一段 $[l,i]$：

• 若该段给第二场，则 dp_pf[i][s] = max(dp_pf[i][s], dp_pf[l-1][s] + cnt[l][i])；
• 若该段给第一场，则需要它提供 cnt[l][i] 个活动，之前已经安排了 max(0, s-cnt[l][i]) 个，故再用此前状态更新即可。

第一行答案枚举 s，取 max_s min(s, dp_pf[T][s]) 即可。

后缀 DP：强制某活动被安排

若要求第 $k$ 个活动必须举行，就意味着我们必须选择一个包含它的区间 $[l,r]$ 并交给某场嘉年华。可枚举所有含有 $k$ 的区间，区间左侧用前缀 DP，右侧用后缀 DP，取二者的 min 即为该选择下的较小活动数。为了把所有区间的值快速取 max，代码中又引入：

• dp_sf[i][s]：处理后缀的对称 DP；
• dp[l][r]：强制最后一段恰好是 $[l,r]$ 时能够取得的最优 min；
• sf[l][r]：从右往左维护 dp[l][r] 的后缀最大值。

查询“活动 $k$ 必须选”时，对所有 $[l,r] \ni k$ 的区间取 sf[l][r] 最大值即可。

复杂度

离散化后最多 $T \le 2n \le 400$，转移中三重循环的复杂度为 $O(T^3)$（常数可控），足够通过题目数据范围。空间消耗同样为 $O(T^2)$。

参考代码

#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define taskname "default"

int s[208], e[208];
int cnt[408][408];
int dp_pf[408][208], dp_sf[408][208];
int dp[408][408], sf[408][408];

vector<int> vec;

void compress() {sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end()) - vec.begin());}
int to_index(int key) {return upper_bound(vec.begin(), vec.end(), key) - vec.begin();}

signed main() {
	// freopen(taskname".inp", "r", stdin);
	// freopen(taskname".out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> s[i] >> e[i];
		e[i] = s[i] + e[i] - 1;
		vec.push_back(s[i]);
		vec.push_back(e[i]);
	}
	compress();
	for (int i = 1; i <= n; ++i) s[i] = to_index(s[i]), e[i] = to_index(e[i]);
	int T = vec.size();
	// cout << T << endl;
	// for (int i = 1; i <= n; ++i) cout << s[i] << ' ' << e[i] << '\n';
	for (int l = 1; l <= T; ++l) for (int r = l; r <= T; ++r) 
		for (int i = 1; i <= n; ++i) cnt[l][r] += (l <= s[i] && e[i] <= r);
	int inf = n * 10;
	for (int i = 1; i <= n; ++i) dp_pf[0][i] = -inf;
	for (int i = 1; i <= T; ++i) {
		dp_pf[i][0] = cnt[1][i];
		for (int s1 = 1; s1 <= n; ++s1) {
			dp_pf[i][s1] = -inf;
			for (int l = 1; l <= i; ++l) {
				dp_pf[i][s1] = max(dp_pf[i][s1], dp_pf[l - 1][s1] + cnt[l][i]);
				dp_pf[i][s1] = max(dp_pf[i][s1], dp_pf[l - 1][max(0, s1 - cnt[l][i])]);
			}
		}
		// for (int j = 0; j <= n; ++j) cout << dp_pf[i][j] << ' ';
		// cout << endl;
	}
	for (int i = 1; i <= n; ++i) dp_sf[T + 1][i] = -inf;
	for (int i = T; i; --i) {
		dp_sf[i][0] = cnt[i][T];
		for (int s1 = 1; s1 <= n; ++s1) {
			dp_sf[i][s1] = -inf;
			for (int r = i; r <= T; ++r) {
				dp_sf[i][s1] = max(dp_sf[i][s1], dp_sf[r + 1][s1] + cnt[i][r]);
				dp_sf[i][s1] = max(dp_sf[i][s1], dp_sf[r + 1][max(0, s1 - cnt[i][r])]);
			}
		}
	}
	int free_ans = 0, cur_ans;
	for (int i = 0; i <= n; ++i) free_ans = max(free_ans, min(i, dp_pf[T][i]));
	cout << free_ans << '\n';
	int x, y;
	for (int l = 1; l <= T; ++l) {
		for (int r = l; r <= T; ++r) {
			x = 0; y = cnt[r + 1][T];
			dp[l][r] = -inf;
			for (x = 0; x <= cnt[1][l - 1]; ++x) {
				dp[l][r] = max(dp[l][r], min(x + y + cnt[l][r], dp_pf[l - 1][x] + dp_sf[r + 1][y]));
				while (y && x + y + cnt[l][r] >= dp_pf[l - 1][x] + dp_sf[r + 1][y]) {
					--y;
					dp[l][r] = max(dp[l][r], min(x + y + cnt[l][r], dp_pf[l - 1][x] + dp_sf[r + 1][y]));
				}
			}
			// cout << l << ' ' << r << ' ' << dp[l][r] << '\n';
		}
		sf[l][n + 1] = -inf;
		for (int r = T; r >= l; --r) sf[l][r] = max(sf[l][r + 1], dp[l][r]);
	}
	for (int i = 1; i <= n; ++i) {
		cur_ans = -inf;
		for (int j = s[i]; j; --j) cur_ans = max(cur_ans, sf[j][e[i]]);
		cout << cur_ans << '\n';
	}
}