本文共 3712 字，大约阅读时间需要 12 分钟。

题目

题目背景
“一次一瓶不是很正常吗？”——瓶瓶牛

题目描述
有 $n$ 个房间，编号为 $1$ 到 $n$ 。有 $n-1$ 个铁门，第 $i$ 个铁门连接房间 $i$ 和 $i+1$ 。

铁门在正常情况下是关闭着的（不然你会被小白活活射死），要打开第 $i$ 个铁门需要有 $a_i$ 个「瓶儿」放在房间 $i$ 的右侧压力板上，或者 $b_i$ 个「瓶儿」放在房间 $i+1$ 的左侧压力板上。

当第 $i$ 个铁门是开着的时候，你可以在 $i$ 和 $i+1$ 房间之间任意移动「瓶儿」。众所周知，一旦「瓶儿」从压力板上离开，铁门会立刻（没有延迟）关上，所以 $i$ 号房间至少剩 $a_i$ 个「瓶儿」，或者 $i+1$ 号房间剩下 $b_i$ 个「瓶儿」。

在房间 $1$ 有一个铁门通往出口，要打开这个隧道需要 $m$ 个「瓶儿」。如果要保证这个铁门不会被打开，最多可以有多少个「瓶儿」（你可以指定他们初始在哪个房间）呢？

数据范围与提示
$n\le 10^3$ 且 $\max (m,a_i,b_i)\le 10^4$ 。提示：此题并不难，只是需要耐心一点。

思路

注：由于题面被魔改过，下文用 “人” 代表「瓶儿」。

可能的情况其实很少。罗列一下就知道了。下面用 $x_1,x_2,\dots ,x_n$ 表示实际上每个房间的人数，用 $f(v)$ 表示「假设没有第一个房间，每个房间中的实际人数是 $v,x_3,x_4,\dots ,x_n$ 时，能够走到 $2$ 号房间（即 $v$ 所在的房间）的最大人数」。

• 门根本打不开。$x_1<a_1$ 且 $f(x_2)<b_1$ 。
• 右边的把左边接过去。$f(x_2)\ge b_1$ 。
  1. 如果 $f(x_2+x_1)\ge b_1+a_1$，可以全部过去，必须 $<m$ 。
  2. 否则，只需要 $f(x_2+x_1)<m+b_1$ 即可。
• 左边的给右边开门。$x_1\ge a_1$ 。
  1. 如果 $f(x_2+x_1-a_1)\ge b_1$，蕴含在 右边把左边接过去 的情况中，不用考虑了。
  2. 无论如何，$f(x_2+x_1-a_1)<m-a_1$ 是有必要的。

其中 $f(x_2+x_1)$ 计算的总人数是没算错的，$f(x_2+x_1-a_1)$ 是少算了 $a_1$ 个的。
$$g^{\prime }(m)=\{\begin{array}{ll}\min (m,a_1)-1+g(b_1)& \\ g(m)& (b_1+a_1<m)\\ g[\min (m+b_1,a_1+b_1)]& \\ g[\min (m-a_1,b_1)]+a_1& \end{array}$$

这些值取 $\max$ 就好了。为啥可以直接取 $\max$ 啊？因为它们都可以还原出一种合法方案。

• $\min (a_1,m)-1+g(b_1)$ 即第一道门永远打不开。
• $g(m)$ 即第一个房间没人，第二个房间也没得 $m$ 个人。纵使 $m\le a_1+b_1$ 也可以转移，因为它显然不会更新答案。
• $g[\min (m+b_1,a_1+b_1)]$ 即第一个房间没人，第二个房间少于 $m+b_1$ 也少于 $a_1+b_1$ 。
• $g[\min (m-a_1,b_1)]+a_1$ 即第一个房间 $a_1$ 个人，第二个房间的人不足以打开门，而一号房间的人打开门之后，第二个房间的人又不足 $m-a_1$，没法逃生。

显然 $m\ge \max (a_i+b_i)$ 无益。复杂度 $\mathcal{O}(n\cdot \max (a_i+b_i,m))$ 。

代码

#include <cstdio> #include <iostream>#include <vector>#include <cstring>using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}inline void writeint(int x){   	if(x > 9) writeint(x/10);	putchar((x-x/10*10)^48);}inline void getMax(int &a,const int &b){   	(a < b) ? (a = b) : 0;}const int MaxN = 1005;const int MaxM = 20005;int dp[2][MaxM], a[MaxN], b[MaxN];int main(){   	int n = readint(), m = readint();	for(int i=1; i<n; ++i){   		a[i] = readint();		b[i] = readint();	}	for(int j=1; j<MaxM; ++j)		dp[n&1][j] = j-1; // less than j	for(int i=n-1; i>=1; --i){   		int fr = (i&1)^1;		for(int j=1; j<MaxM; ++j){   			dp[i&1][j] = min(a[i],j)-1+dp[fr][b[i]];			if(a[i] <= j) getMax(dp[i&1][j],				dp[fr][min(j-a[i],b[i])]+a[i]);			getMax(dp[i&1][j],dp[fr][j]);			getMax(dp[i&1][j],dp[fr][min(j,a[i])+b[i]]);		}	}	printf("%d\n",dp[1][m]);	return 0;}

后记

是从前往后 $\mathtt{d}\mathtt{p}$ 的，听上去很离谱，对吧？

其实它是这样的：在从右往左走的过程中，后面的房间会剩下 $b_i$ 个人，这是成长的代价。那么我们从左往右，把 $b_i$ 个人放好，就行了。（本质是 操作可逆，时光倒流，如同。）