我震惊了，我好菜，我是不是该退役（苦逼）
可以先看看代码里的注释
首先我们先考虑一下第一问好了真做起来也就这个能想想了
那么离散化时间是肯定的，看一手范围猜出是二维DP，那对于两个会场，一个放自变量，一个放变量，然后O(n^3)的DP好了
第二问像第一问的做法特判一波就是O(n^4)啦
对于一个嘉年华必选，等价于必选一段区间，我们设f[l][r]为必选l,r放一起，前面一段自己处理，后面一段自己处理的最优解
那么ans=max(f[l][r]) (a[i].l<=l,r<=a[i].r)
可以发现前面一段自己处理我们在第一问已经搞定了。。。后面高仿前面就好。。。
f[l][r]=max(min(s[l-1][x]+h[l][r]+t[r+1][y],x+y))
然后这还是个四方的
但是用脑(bai)子(du)想想，t[r+1][y]随y增大减小，把min中两项写成两个一次函数，这个min的图像会是一个v字形（一个下降的直线和一个上升的直线），v的最下方就是决策点
当x增大的时候由于s[l-1][x]也跟着减小，相当于前一个截距变小，而后一个截距变大，决策点左移，所以是有决策单调性的y可以扫一遍完事
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=;
const int maxT=*maxn; struct node{int l,r;}a[maxn];
int lslen,ls[maxT]; int h[maxT][maxT];//时间段内------->有多少嘉年华
int s[maxT][maxn],t[maxT][maxn];//前/后到i的时间段，给第一个j，另一个最多混到多少
int f[maxT][maxT];//这个时间段必选，且没有选择和该时间段相交的嘉年华------>较小的最大为多少
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);a[i].r+=a[i].l;
a[i].l++;
ls[++lslen]=a[i].l;
ls[++lslen]=a[i].r;
}
sort(ls+,ls+lslen+);
lslen=unique(ls+,ls+lslen+)-ls-;
for(int i=;i<=n;i++)
a[i].l=lower_bound(ls+,ls+lslen+,a[i].l)-ls,
a[i].r=lower_bound(ls+,ls+lslen+,a[i].r)-ls; for(int l=;l<=lslen;l++)
for(int r=l;r<=lslen;r++)
for(int i=;i<=n;i++)
if(l<=a[i].l&&a[i].r<=r)h[l][r]++; //.......init........ memset(s,-,sizeof(s));s[][]=;
for(int i=;i<lslen;i++)
for(int j=;j<=n;j++)
if(s[i][j]!=-)
for(int k=i+;k<=lslen;k++)
s[k][j]=max(s[k][j],s[i][j]+h[i+][k]),
s[k][j+h[i+][k]]=max(s[k][j+h[i+][k]],s[i][j]);
int mx=;
for(int j=;j<=n;j++)
mx=max(mx,min(j,s[lslen][j]));
printf("%d\n",mx); memset(t,-,sizeof(t));t[lslen+][]=;
for(int i=lslen+;i>;i--)
for(int j=;j<=n;j++)
if(t[i][j]!=-)
for(int k=i-;k>=;k--)
t[k][j]=max(t[k][j],t[i][j]+h[k][i-]),
t[k][j+h[k][i-]]=max(t[k][j+h[k][i-]],t[i][j]); //......solve1....... for(int l=;l<=lslen;l++)
for(int r=l;r<=lslen;r++)
{
int y=n;
for(int x=;x<=n;x++)
{
if((x+y)<=n)
f[l][r]=max(f[l][r],min(s[l-][x]+h[l][r]+t[r+][y],x+y));
while(y>=&&((x+y)>n||s[l-][x]+h[l][r]+t[r+][y]<x+y))
{
y--;
f[l][r]=max(f[l][r],min(s[l-][x]+h[l][r]+t[r+][y],x+y));
}
}
} for(int i=;i<=n;i++)
{
int ans=;
for(int l=;l<=a[i].l;l++)
for(int r=a[i].r;r<=lslen;r++)
ans=max(ans,f[l][r]);
printf("%d\n",ans);
} return ;
}