讲解 P1973 [NOI2011] NOI 嘉年华。

考虑先将时间离散化，使用动态规划算法，使用数据结构，指针加速优化。

思路：

先将时间进行离散化，设总时间为 \(cnt\)，然后考虑求出 \(W(l,r)\)，即在时间段 \([l,r]\) 内的所有节目，可以 \(n^2\) 前缀和，也可以 \(n^3\) 暴力。

然后定义 \(f_{i,j}\) 表示前 \(i\) 个时间，一号场地有 \(j\) 个节目时，二号场地最多的节目数量，则状态转移方程为：

\[f_{i,j} = \max\limits_{k=0}^{i-1} \max(f_{k,j} + W(k,i),f_{k,j-W(k,i)})

\]

那么可以得到：

\[ans_0 = \max\limits_{i=0}^n \min(i,f_{cnt,i})

\]

则第一个问的时间复杂度为 \(O(N^3)\)。

然后再看第二个问，需要定义 \(g_{i,j}\) 表示 \(i \sim cnt\) 的时间段，一号场地有 \(j\) 个节目时，二号场地最多的节目数量，则状态转移方程类似：

\[g_{i,j} = \max\limits_{k=i+1}^{cnt} \max(g_{k,j} + W(i,k),g_{k,j-W(i,k)})

\]

然后再定义 \(dp_{l,r}\) 表示若强制选 \([l,r]\) 的全部节目的局部最优解，则可以枚举左边和右边一号场有多少个进行转移：

\[dp_{l,r} = \max\limits_{i=0}^n \max\limits_{j=0}^n \min(i+W(l,r)+j,f_{l,i} + g_{r,j})

\]

那么此时若强制选 \([l,r]\) 的答案，是 \(dp_{l,r}\) 吗？答案很明显，不是。

因为 \(f_{l-1,i}\) 和 \(g_{r+1,j}\) 只保证了 \(1 \sim l-1,r+1 \sim j\) 的局部最优，即可能会有一些活动的一端在 \([l,r]\) 内，但是另一端不在 \([l,r]\) 内，此时选这些节目可能会更优。

于是我们需要枚举一个 \([L,R]\)，使得 \([L,R]\) 包含 \([l,r]\)，故 \([l,r]\) 强制选的答案为：

\[\max_{L=1}^l \max_{R=r}^{cnt} dp_{L,R}

\]

故只要我们求出 \(dp\)，就可以 \(O(N^3)\) 的得到答案。

但是计算 \(dp\) 的时间复杂度为 \(O(N^4)\)，且常数较大，需要优化卡常大师应该能冲过去。

注意到 \(f_{l,i}\) 和 \(g_{r,j}\) 是会随着 \(i/j\) 的增大而不增的。

此时若 \(i\) 不动，则对于 \(j\) 来说， \(i+W(l,r)+j\) 是单增的，\(f_{l,i} + g_{r,j}\) 是单降的，故 \(H(y)=\min(i+W(l,r)+j,f_{l,i} + g_{r,j})\) 是一个单峰的函数，我们需要找到其最大值。

故我们可以对 \(j\) 进行走指针，从 \(yjn\) 开始，若 \(H(j-1)\ge H(j)\)，就可以令 \(j \gets j - 1\)。

这里需要证明一下在 \(i\) 增加时，\(j\) 的单峰函数只会向左平移，因为这样才可以走指针：

在 \(i\) 增加时，\(i+W(l,r)+j\) 也会增加。

而对于 \(f_{l,i}+g_{r,j}\) 不增。

故会峰点左移。

总时间复杂度是 \(O(N^3)\)。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const int N=205,M=410,INF=1e9;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

struct Seg{

int l,r;

int id;

}A[N];

int n,cnt,Max;

int ans[N],s[N],h[M];

int F[M][N],G[M][N],dp[M][M],W[M][M];

int get(int i,int j,int l,int r){

return min(i+W[l][r]+j,F[l][i]+G[r][j]);

}

bool End;

int main(){

//open("A.in","A.out");

n=read();

for(int i=1;i<=n;i++){

A[i].l=read(),A[i].r=A[i].l+read();

A[i].id=i;

h[++cnt]=A[i].l;

h[++cnt]=A[i].r;

}

sort(h+1,h+cnt+1);

cnt=unique(h+1,h+cnt+1)-(h+1);

for(int i=1;i<=n;i++){

A[i].l=lower_bound(h+1,h+cnt+1,A[i].l)-h;

A[i].r=lower_bound(h+1,h+cnt+1,A[i].r)-h;

}

for(int l=1;l<=cnt;l++)

for(int r=l;r<=cnt;r++)

for(int i=1;i<=n;i++)

if(l<=A[i].l&&A[i].r<=r)

W[l][r]++;

for(int i=0;i<=cnt;i++)

for(int j=0;j<=n;j++)

F[i][j]=-INF;

F[0][0]=0;

for(int i=1;i<=cnt;i++)

for(int j=0;j<=n;j++)

for(int k=0;k<i;k++)

F[i][j]=max({F[i][j],F[k][j]+W[k][i],(j>=W[k+1][i])?(F[k][j-W[k][i]]):(-INF)});

for(int i=1;i<=cnt+1;i++)

for(int j=0;j<=n;j++)

G[i][j]=-INF;

G[cnt+1][0]=0;

for(int i=cnt;i>=1;i--)

for(int j=0;j<=n;j++)

for(int k=i+1;k<=cnt+1;k++)

G[i][j]=max({G[i][j],G[k][j]+W[i][k],(j>=W[i+1][k])?(G[k][j-W[i][k]]):(-INF)});

for(int l=1;l<=cnt;l++){

for(int r=l;r<=cnt;r++){

for(int x=0,y=n;x<=n;x++){

while(y&&get(x,y-1,l,r)>=get(x,y,l,r))

y--;

dp[l][r]=max(dp[l][r],get(x,y,l,r));

}

}

}

for(int i=0;i<=n;i++)

ans[0]=max(ans[0],min(i,F[cnt][i]));

for(int i=1;i<=n;i++)

for(int L=1;L<=A[i].l;L++)

for(int R=A[i].r;R<=cnt;R++)

ans[i]=max(ans[i],dp[L][R]);

for(int i=0;i<=n;i++){

write(ans[i]);

putchar('\n');

}

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}