首先,将时间离散化。设离散化后的时间区间为$[1,T]$,其中$t\leq 2n$。之后先预处理$inter[i][j]$表示完全在时间i到时间j之间举行的活动个数。
容易想到最简单的DP,$f[i][j],g[i][j]$,分别表示在区间$[1,i]$和$[i,T]$,一个会场至少举办j个活动的情况下,另一个会场至少举办多少个活动?转移就是枚举一个区间,将其中所有活动分配给某个会场。
这样一来,第一问答案可以由$\max_{j}\min(f[T][j],j)$确定。
对于第二问,如何强制让一个会场举办第i个活动? 我们可以选一个包含第i个活动的区间$[L,R]$,然后强制第一个会场举办所有在$[L,R]$之间举行的活动。并枚举在$[1,L]$与$[R,T]$这两段区间第一个会场举办的活动个数$x,y$。答案就是
$$\max_{L,R,x,y} \min(x+inter[L][R]+y,f[L][x]+g[R][y])$$。
但粗略地看起来时间复杂度很大,对于每个$k$,都要四重循环计算答案,时间复杂度是$O(n^5)$。注意到,我们可以直接计算数组
$$ans[L][R]=\max_{L,R,x,y} \min(x+inter[L][R]+y,f[L][x]+g[R][y])$$。这样就把时间复杂度降到了$O(n^4)$。
似乎对于200还是有些困难,更进一步,注意到,$f[L][x]$和$g[R][y]$分别是关于$x$和$y$的减函数。所以对于固定的$L,R$,
当$x$变大时,最优的$y$应该变小才能使答案更好。这样一来,将y作为一个随x增加而递减的指针即可。时间复杂度为$O(n^3)$。
当然,如果你嫌麻烦,或者考场上没想到这里,直接$n^4$枚举答案,加上一些很容易想到的剪枝,可以把常数控制得极小,也能轻松通过本题。。。。。。。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int const N=401,M=101,INF=1e6;
int n,t,a[N],b[N],u[N],v[N],p[N],q[N],inter[N][N],
f[N][N],g[N][N],ans[N];
int main(){
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i]>>b[i];
b[i]+=a[i];
p[++t]=a[i];
p[++t]=b[i];
}
sort(p+1,p+1+t);
q[1]=1;
for (int i=2;i<=t;i++)
if (p[i]==p[i-1]) q[i]=q[i-1]; else q[i]=q[i-1]+1;
for (int i=1;i<=n;i++)
for (int j=1;j<=t;j++) {
if (a[i]==p[j]) u[i]=q[j];
if (b[i]==p[j]) v[i]=q[j];
}
t=q[t];
for (int i=1;i<=t;i++)
for (int j=i+1;j<=t;j++)
for (int k=1;k<=n;k++)
if (u[k]>=i && v[k]<=j) inter[i][j]++;
for (int i=1;i<=t;i++)
for (int j=0;j<=n/2;j++){
f[i][j]=-INF;
if (j==0) f[i][j]=inter[1][i];
for (int k=1;k<=i-1;k++){
f[i][j]=max(f[i][j],f[k][j]+inter[k][i]);
f[i][j]=max(f[i][j],f[k][max(0,j-inter[k][i])]);
}
}
for (int i=t;i>=1;i--)
for (int j=0;j<=n/2;j++){
g[i][j]=-INF;
if (j==0) g[i][j]=inter[i][t];
for (int k=i+1;k<=t;k++){
g[i][j]=max(g[i][j],g[k][j]+inter[i][k]);
g[i][j]=max(g[i][j],g[k][max(0,j-inter[i][k])]);
}
}
for (int k=1;k<=n;k++){
for (int i=u[k];i>=1;i--)
for (int j=v[k];j<=t;j++){
for (int l=0;l<=inter[1][i];l++){
for (int r=0;r<=inter[j][t];r++){
ans[k]=max(ans[k],min(l+r+inter[i][j],f[i][l]+g[j][r]));
if (g[j][r]<r) break;
}
if (f[i][l]<l) break;
}
if (inter[1][i]+inter[j][t]<ans[k]) break;
if (inter[i][j]>inter[1][i]+inter[j][t]) break;
}
ans[0]=max(ans[0],ans[k]);
}
for (int k=0;k<=n;k++)
cout<<ans[k]<<endl;
return 0;
}
```