Description
给你 $n$ 个区间,让你选出其中一些分为两组,要求两组区间不能有交集,组内可以有交集。让你最大化两组之间区间个数较小的那一组的选取区间个数。以及对于每个区间 $i$,回答第 $i$ 个区间必选(放在第一组或者第二组),两组个数的最小值的最大值。
$1\leq n\leq 200$
Solution
首先,可以知道每组一定是若干个连续的时间段组成的。那么我们可以按时间来 DP,先离散化,设时间上限为 $T$。
为了方便转移,我们记 $cnt_{i,j}$ 为全在 $[i,j]$ 时间段内的区间个数。这个是可以在 $O(n^3)$ 内预处理出来的。
记 $f_{i,j}$ 表示 $1\sim i$ 时间段,第一组有 $j$ 个区间时第二组最多有多少个区间。首先,若 $i$ 这个时刻不选,可以继承 $i-1$ 时刻的状态,那么赋值 $f_{i,j}=f_{i-1},j$。
考虑转移就是枚举以 $i$ 为右端点,$k$ 为左端点,这一整个时间段放在第一组或是第二组,显然对于每个 $k$,$f_{i,j}=\max{f_{k-1,j}+cnt_{k,i},f_{k-1,j-cnt_{k,i}}}$。
那么第一问的答案显然就是 $\max\limits_{0\leq i\leq n}\min{i,f_{T,i}}$。
考虑第二问,首先我们仿照 $f$ 的定义用相同的方式 DP 出一个数组 $g$,表示 $i\sim T$ 时间段,第一组有 $j$ 个区间时第二组最多有多少个区间。
那么对于第 $i$ 个区间,因为它必须被选,那么去考虑选择哪些时间段是包含第 $i$ 个区间的。用 $O(n^2)$ 去枚举端点 $[l,r]$,另外考虑 $1\sim l-1$ 中放 $a$ 个在第一组,$r+1\sim T$ 中放 $b$ 个在第一组。考虑 $[l,r]$ 放在第一组还是第二组,显然答案就是 $\max\limits_{l,r,a,b}{\min{f_{l-1,a}+g_{r+1,b}+cnt_{l,r}, a+b}, \min{f_{l-1,a}+g_{r+1,b}, a+b+cnt_{l,r}}}$。不过这样,单个询问就是 $O(n^4)$ 的,吃不消。
容易发现上述计算时会有许多冗余重复的计算,那么我们考虑预处理一个数组 $dp_{i,j}$ 表示 $[i,j]$ 区间必选,最大化最小区间个数的值。
显然对于每个 $i,j$,我们只需枚举 $1\sim i-1$ 中放在第一组个数 $a$,$j+1\sim T$ 中放在第一组个数 $b$。不过预处理这个数组还是 $O(n^4)$ 的。
值得注意的是 $f_{i,j}$ 随 $j$ 增大,$f$ 值单调不增。利用这个单调性,可以双指针优化,枚举 $a$ 时,继承 $b$ 值。最终复杂度为 $O(n^3)$。
预处理完,之后只需 $O(n^2)$ 枚举端点就可以计算答案了。
综上复杂度为 $O(n^3)$。
Code
#include <bits/stdc++.h>
#define inf (-f[N-1][N-1])
using namespace std;
const int N = 405;
int n, l, r, f[N][N], b[N], tot, cnt[N][N], g[N][N], dp[N][N];
struct tt {
int l, r;
} a[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &l, &r),
b[++tot] = a[i].l = l, b[++tot] = a[i].r = l+r-1;
sort(b+1, b+tot+1);
tot = unique(b+1, b+tot+1)-b-1;
for (int i = 1; i <= n; i++)
a[i].l = lower_bound(b+1, b+tot, a[i].l)-b,
a[i].r = lower_bound(b+1, b+tot, a[i].r)-b;
for (int i = 1; i <= tot; i++)
for (int j = i; j <= tot; j++)
for (int k = 1; k <= n; k++)
cnt[i][j] += (i <= a[k].l && a[k].r <= j);
memset(f, 192, sizeof(f));
memset(g, 192, sizeof(g));
f[0][0] = 0;
for (int i = 1; i <= tot; i++)
for (int j = 0; j <= n; j++) {
f[i][j] = f[i-1][j];
for (int k = i; k >= 1; k--) {
f[i][j] = max(f[i][j], f[k-1][j]+cnt[k][i]);
if (j >= cnt[k][i]) f[i][j] = max(f[i][j], f[k-1][j-cnt[k][i]]);
}
}
g[tot+1][0] = 0;
for (int i = tot; i >= 1; i--)
for (int j = 0; j <= n; j++) {
g[i][j] = g[i+1][j];
for (int k = i; k <= tot; k++) {
g[i][j] = max(g[i][j], g[k+1][j]+cnt[i][k]);
if (j >= cnt[i][k]) g[i][j] = max(g[i][j], g[k+1][j-cnt[i][k]]);
}
}
int ans = -inf;
for (int j = 0; j <= n; j++)
ans = max(ans, min(j, f[tot][j]));
printf("%d\n", ans);
for (int i = 1; i <= tot; i++)
for (int j = i; j <= tot; j++) {
int l = cnt[1][i-1];
for (int r = 0; r <= cnt[j+1][tot]; r++) {
while (l && max(min(f[i-1][l]+g[j+1][r]+cnt[i][j], l+r), min(f[i-1][l]+g[j+1][r], l+r+cnt[i][j]))
<= max(min(f[i-1][l-1]+g[j+1][r]+cnt[i][j], l-1+r), min(f[i-1][l-1]+g[j+1][r], l-1+r+cnt[i][j]))) --l;
dp[i][j] = max(dp[i][j], max(min(f[i-1][l]+g[j+1][r]+cnt[i][j], l+r), min(f[i-1][l]+g[j+1][r], l+r+cnt[i][j])));
}
}
for (int i = 1; i <= n; i++) {
int ans = 0;
for (int l = 1; l <= a[i].l; l++)
for (int r = a[i].r; r <= tot; r++)
ans = max(ans, dp[l][r]);
printf("%d\n", ans);
}
return 0;
}