前言

noip 模拟赛 T2 放这种题，出题人你这辈子有了。

noip 模拟赛 T2，场上 130 个人中过了 20 多个。

观察

首先注意到操作是可逆的。并且，如果有 $x$ 个生物闯入了一个房间，并带着 $y(y\ge x)$ 个生物回到这个房间，那么这 $y$ 个生物也能闯回去。

其次我们注意到，这个问题等价于安放尽可能多的生物，使得没有任何一个生物可以到达自己起点更靠左的地方（或者离开）。

再其次我们注意到值域很小。

解法

如果我们钦定了前几个房间的生物单靠自己无法往左移动，那么它们肯定会往右侧 rush，试图解救右侧房间的生物并原路返回。

考虑动态规划。设 $f_{i,j}$ 为对于前 $i$ 个房间，在没有生物可以往左走且最大有 $j$ 个生物可以聚集在第 $i$ 个房间的情况下，这些房间总共最多可以放多少个生物（无解记为 $-\infin$）。

边界为 $\forall 0\le j<m,f_{1,j}=j$ 以及 $\forall m\le j,f_{1,j}=-\infin$。

接下来对于 $\forall 1\le i<n$，设 $x,z$ 为第 $i,i+1$ 个房间内最多聚集的生物数，$y$ 为第 $i+1$ 个房间内的生物数，则：

• 显然 $y\le b_i$。

• 如果 $x<a_i$，那么：

  • 若 $y<b_i$，则左边的生物过不来，$z=y$。
  • 若 $y=b_i$，则左边的生物能过来，$z=x+y$。

• 如果 $a_i\le x<a_i+b_i$，那么 $y=0$，不然这边的生物就往左走了。同时，左边会留下 $a_i$ 个生物，并且使其它的生物闯入右边，$z=x-a_i$。

• 如果 $x\ge a_i+b_i$，那么 $y=0$，且左边的生物全部可以闯入右边，$z=x$。

记 $A$ 为值域。注意到在合法的情况下最多聚集 $2A$ 个生物，那么分讨并 dp 即可。时间复杂度 $O(nA)$。

代码

代码非常短。

#include<bits/stdc++.h>
using namespace std;

int cid,T,n,m,a[2005],b[2005];
int M=40000,f[40005],g[40005];

int main(){
	cin>>n>>m;m--;
	for(int i=1;i<n;i++)cin>>a[i]>>b[i];
	memset(f,0xb0,sizeof(f));memset(g,0xb0,sizeof(g));
	for(int j=0;j<=M;j++)f[j]=(j<=m?j:0xb0b0b0b0);
	for(int i=1;i<n;i++){
		for(int j=0;j<=M;j++)g[j]=f[j];
		for(int j=b[i];j<a[i]+b[i];j++)f[j]=max(f[j],g[j-b[i]]+b[i]);
		for(int j=a[i];j<a[i]+b[i];j++)f[j-a[i]]=max(f[j-a[i]],g[j]);
		int mxm=0xb0b0b0b0;for(int j=0;j<a[i];j++)mxm=max(mxm,g[j]);
		for(int j=0;j<b[i];j++)f[j]=max(f[j],mxm+j);
	}
	int ca=0xb0b0b0b0;for(int j=0;j<=M;j++)ca=max(ca,f[j]);
	cout<<ca<<'\n';
	return 0;
}