知识点: DP，单调性优化

原题面

写在前面

\(\text{Updated on 2020.8.27}\)
被 Itst 叉掉 啦！修改了不精细的代码实现 和 部分不严谨的用词。

参考: stO FlashHu 的题解 Orz

蒟蒻主要是想更详细地分析一下单调性优化。
尽量把悟到的信息都放了上来，水平不够，比较啰嗦，望见谅。

---

题意简述:

给定 \(n\) 个事件，第 \(i\) 个事件从 \(S_i\)时刻开始，持续 \(T_i\) 时刻。
可将它们分到两个地点中的一个，或者放弃。
同一地点事件可同时发生，两个事件不可同时发生在不同地点。
求

1. 无限制时，事件数较小的地点 的事件数。
2. 不放弃第 \(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\)，则有：

\[pre_{i,j} = \max_{k=1}^{i}\{pre _{k,j} + cnt_{k,i},\ pre_{k,j-cnt_{k,i}}\}\]

两种情况分别代表将区间 \([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}\) 类似，即为：

\[suf_{i,j} = \max_{k=i}^{m}\{suf_ {k,j} + cnt_{k,i},\ suf_{k,j-cnt_{k,i}}\}\]

---

考虑必选事件 \((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}\)。

则有状态转移方程：

\[f_{l,r} = \max_{x=0}^{n}\max_{y=0}^{n}\{\min(x + cnt_{l,r} + 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 
#include 
#include 
#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;
}