知识点: DP，单调性优化
写在前面
\(\text{Updated on 2020.8.27}\)
被 Itst 叉掉 啦！修改了不精细的代码实现 和 部分不严谨的用词。
参考: stO FlashHu 的题解 Orz
蒟蒻主要是想更详细地分析一下单调性优化。
尽量把悟到的信息都放了上来，水平不够，比较啰嗦，望见谅。
题意简述:
给定 \(n\) 个事件，第 \(i\) 个事件从 \(S_i\)时刻开始，持续 \(T_i\) 时刻。
可将它们分到两个地点中的一个，或者放弃。
同一地点事件可同时发生，两个事件不可同时发生在不同地点。
求
- 无限制时，事件数较小的地点 的事件数。
- 不放弃第 \(i\) 个事件时，事件数较小的地点 的事件数。
\(1\le n \le 200, 0\le S_i\le10^9,1\le T_i\le 10^9\)。
分析题意
先离散化，下文中出现的 “时间” 均指离散化后的值，其最大值 \(\le 2n\)。
把事件看做线段，地点看做集合。
从 \(S_i\)时刻开始，持续 \(T_i\) 时刻的 事件 记为 \((s_i,t_i)\)，它对应着 线段 \([s_i,s_i+t_i]\)。
有一个很显然的结论：
对于一个分配方案，若存在某被丢弃的线段，可加入到集合中。
将其加入，答案不会变劣。
由上，若向某一集合中添加了一条线段 \([L,R]\)，则所有包含于 \([L,R]\) 的线段，都一定会被添加到该集合中。
考虑将一个区间内的完整线段合并，
设 \(cnt_{i,j}\) 表示区间 \([i,j]\) 内的完整线段数。
暴力 \(O(n^3)\) 预处理即可。
先搞掉子任务一。
要求：事件数较小的地点 的事件数。
数据范围不大，考虑枚举一边的事件数，并求另一边的最大值，两边取 \(\min\) 即为所求。
设 \(pre_{i,j}\) 表示，枚举到时间 \(i\)，一边线段数为 \(j\) 时，另一边线段数的最大值。
转移时枚举断点 \(k\)，则有：
两种情况分别代表将区间 \([k,i]\) 内的线段添加到两边的情况。
转移的总复杂度为 \(O(n^3)\)。
令 \(m\) 为时间的最大值，显然答案为 \(\max\limits_{j=1}^{n}\{\min(pre_{m,j},j)\}\)。
再搞子任务二。
\(pre_{i,j}\)，即为 \(1\sim i\) 中，一边线段数为 \(j\) 时，另一边线段数的最大值。
再处理一个 \(suf_{i,j}\)，表示 \(i\sim m\) 中，一边线段数为 \(j\) 时，另一边线段数的最大值。
转移方程与 \(pre_{i,j}\) 类似，即为：
考虑必选事件 \((s_i,t_i)\) 的答案。
此时被区间 \([s_i,s_i+t_i]\) 包含的线段，必被选入同一集合，但\(s_i\) 之前和 \(t_i\) 之后选择的线段数 未知。
同子任务一的思路，考虑枚举线段数，并求另一集合线段数的最大值，两边取 \(\min\) 即为所求。
设 \(f_{l,r}\) 为保证一边必选区间 \([l,r]\) 中线段时，最优的答案。
枚举 \(x\) 代表这一集合中被 \([1,l-1]\) 包含的线段数， \(y\) 为 \([r+1,m]\) 中的线段数。
这一集合线段总数即为 \(x + cnt_{i,j} + y\)。
另一集合选择的最大个数，显然为 \(pre_{l,x} + suf_{r,y}\)。
则有状态转移方程：
这里有一个坑点。
在将一个区间内的完整线段合并这一前提下，枚举的 \(x,y\) 的值不一定合法。
考虑这样一种情况：
活动 则赛和华赛的起止时间均相同。
\([l,r]\) 内的东方鬼畜音 Mad 大赏必须选择，考虑枚举\([r+1,m]\) 内与它在同一会场的活动数 \(y\)。
显然，\(y=1\) 的情况是不合法的。
由一开始的处理可知，则赛和华赛两活动，必在同一会场举办。
区间 \([r+1,m]\) 中不可能仅选出 \(1\) 条线段，故 \(y=1\) 不合法。
可考虑预处理出 bool 数组 able[l][r][x] 表示区间 \([l,r]\) 内是否可以选出 \(x\) 条线段，从而判断枚举的 \(x,y\) 是否合法。
在预处理 \(cnt\) 时可顺便维护。
所以答案就是 \(f_{s_i,t_i}\) 吗？回答是否定的。
还有一种特殊情况：
当 \([s_i,s_i+t_i]\) 被一属于同一集合的某线段包含，即存在 包含询问区间 的线段时，上述 \(pre_{l,x} + suf_{r,y}\) 的计算方法就不合适了。
考虑枚举这样的线段，以包含所有特殊情况。
显然，第 \(i\) 个事件必选的答案即为：\(\max\limits_{l=1}^{s_i}\max\limits_{l=t_i}^{m}f_{l,r}\)。
这样就必须预处理出所有 \(f_{i,j}\)，其复杂度达到 \(O(n^4)\)，会被卡掉。
考虑一波优化。
显然， \(pre_{l,x}\) 随 \(x\) 的增加而减小，\(suf_{r,y}\) 随 \(y\) 的增加而减小。
当一边选的多了，另一边选择的余地自然少。
观察上面的式子，答案即最大的 \(\min(x + cnt_{l,r} + y,\ pre_{l,x} + suf_{r,y})\)，考虑如何最大化它的值。
当 \(x\) 固定时，\(x + cnt_{l,r}\) 与 \(pre_{l,x}\) 均不变。
正序枚举 \(y\)，\(suf_{r,x}\) 递减。此时 有\((x + cnt_{l,r} + y)\uparrow\) 而 \((pre_{l,x} + suf_{r,y})\downarrow\)。
讨论一波，显然有下图形式：
它是一关于 \(y\) 的单峰函数。在峰值左侧有 \(x + cnt_{l,r} + y< pre_{l,x} + suf_{r,y}\)，函数递增。右侧则相反。
当 \(x\) 增加时，\(x + cnt_{l,r}\) 增加，\(pre_{l,x}\) 减小。单峰函数的极值会在 \(y\) 更小时取到，有：
发现 在 \(x\) 增加时，令答案更优的 \(y\) 单调递减。
则可在正序枚举 \(x\) 的同时，设立一指针指向 最优的 \(y\)，单调左移即可。
省去一层循环，复杂度 \(O(n^3)\)，期望得分 \(100\text{pts}\)。
代码实现
调了很久发现是离散化挂掉了
//知识点:DP
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <algorithm>
#define max std::max
#define min std::min
#define ll long long
#define Calc(y) (min(x+cnt[l][r]+y,pre[l][x]+suf[r][y]))
const int kMaxn = 210;
const int kMaxm = 410;
const int kInf = 1e9 + 2077;
//=============================================================
struct Plan {
int S, T; //开始时间，结束时间
} p[kMaxn], tmp[kMaxn];
int data[kMaxm];
int n, max_time, ans, cnt[kMaxm][kMaxm];
//pre:1~i内一边选j个，另一边选择的最大值。 suf:i~m
int pre[kMaxm][kMaxn], suf[kMaxm][kMaxn];
int f[kMaxm][kMaxm];
bool able[kMaxm][kMaxm][kMaxn];
//able[l][r][x]：在上述合并的前提下，区间 [l,r] 是否可以选出 x 条线段。
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool Compare(Plan fir, Plan sec) {
if (fir.S != sec.S) return fir.S < sec.S;
return fir.T < sec.T;
}
void Prepare() {
n = read();
for (int i = 1; i <= n; ++ i) {
data[++ max_time] = p[i].S = read();
data[++ max_time] = p[i].T = read() + p[i].S;
}
std :: sort(data + 1, data + max_time + 1);
max_time = std :: unique(data + 1, data + max_time + 1) - data - 1;
for (int i = 1; i <= n; ++ i) {
p[i].S = std :: lower_bound(data + 1, data + max_time + 1, p[i].S) - data;
p[i].T = std :: lower_bound(data + 1, data + max_time + 1, p[i].T) - data;
}
for (int i = 1; i <= n; ++ i) tmp[i] = p[i];
std :: sort(tmp + 1, tmp + n + 1, Compare);
for (int i = 1; i <= n; ++ i) {
for (int l = 1; l <= tmp[i].S; ++ l) {
for (int r = tmp[i].T; r <= max_time; ++ r) {
able[l][r][0] = true;
able[l][r][++ cnt[l][r]] = true;
//有多个相同的区间，在合并的前提下，要么同时选择它们，要么都不选。
//故将 cnt[l][r] - 1 置为 false。
if (tmp[i].S == tmp[i - 1].S && tmp[i].T == tmp[i - 1].T) {
able[l][r][cnt[l][r] - 1] = false;
}
}
}
}
}
//=============================================================
int main() {
Prepare();
for (int i = 1; i <= max_time; ++ i) {
for (int j = 1; j <= n; ++ j) {
pre[i][j] = suf[i][j] = - kInf;
}
}
for (int i = 1; i <= max_time; ++ i) {
for (int j = 0; j <= cnt[1][i]; ++ j) { //一边的数量
for (int k = 1; k <= i; ++ k) { //枚举上一个时间点
pre[i][j] = max(pre[i][j], pre[k][j] + cnt[k][i]);
if (j >= cnt[k][i]) pre[i][j] = max(pre[i][j], pre[k][j - cnt[k][i]]);
}
}
}
for (int i = max_time; i >= 1; -- i) {
for (int j = 0; j <= cnt[i][max_time]; ++ j) { //一边的数量
for (int k = i; k <= max_time; ++ k) { //枚举上一个时间点
suf[i][j] = max(suf[i][j], suf[k][j] + cnt[i][k]);
if (j >= cnt[i][k]) suf[i][j] = max(suf[i][j], suf[k][j - cnt[i][k]]);
}
}
}
for (int i = 1; i <= n; ++ i) ans = max(ans, min(pre[max_time][i], i));
printf("%d\n", ans);
for (int l = 1; l <= max_time; ++ l) {
for (int r = l + 1; r <= max_time; ++ r) {
for (int y = n, x = 0; x <= n; ++ x) {
if (! able[1][x]) continue;
int best = Calc(y), now;
while (y) { //y单调左移，直到指向最优的 y
if (! able[r + 1][max_time][y - 1]) {
y --;
continue;
}
if (best > (now = Calc(y - 1))) break;
best = now, -- y;
}
//错误写法：while (y && best <= (now = Calc(y - 1))) best = now, -- y;
f[l][r] = max(f[l][r], Calc(y));
}
}
}
for (int i = 1; i <= n; ++ i) { //回答询问
ans = 0;
for (int l = 1; l <= p[i].S; ++ l) {
for (int r = max_time; r >= p[i].T; -- r) {
ans = max(ans, f[l][r]);
}
}
printf("%d\n", ans);
}
return 0;
}