Description：

有 $n$ 个人，每个人有肩高和臂长，每个人可以踩在另一个人的肩上，想逃出高位 $H$ 的坑，问最多能有多少人出去。

$1\leqslant n\leqslant 2000$

Solution：

参考题解

设肩高为 $A_i$ ，臂长为 $B_i$ ，首先证明一个结论，就是跳出坑的顺序一定是按 $A_i+B_i$ 从小到大的，证明一下：

设剩下的肩高的和为 $SA$ ，那么 $x$ 能在 $y$ 之前跳出去当且仅当满足 $SA+A_y+A_x+B_x\geqslant H$ 且 $SA+A_y+B_y\geqslant H$ ，也就是 $SA\geqslant H-A_y-\min(A_x+B_x,B_y)$ ，那么当 $H-\min(A_x+B_x+A_y,A_y+B_y)\leqslant H-\min(A_y+B_y+A_x,A_x+B_x)$ 时， $x$ 在 $y$ 之前出去需要的 $SA$ 更小，也就更有可能都出去，用国王游戏的思想整理一下发现就是 $A_x+B_x\leqslant A_y+B_y$ 。

已知出去的顺序，那么就可以 $DP$ 了，具体的做法就是类似背包的做法，设 $f[i][j]$ 表示前 $i$ 个人跳出去了 $j$ 个最高能堆多高，转移为：

$f[i][j]=\max(f[i-1][j-1](f[i-1][j-1]+A_i+B_i+sufh[i+1]\geqslant H),f[i-1][j]+A_i)$

因为要按顺序跳，所以后面的一定都还没跳，因此记一个后缀和 $sufh$ 不会有问题。

总结一下这道题就是主要思想是 $DP$ ，但是直接 $DP$ 正确性没保证（因为 $sufh$ 没保证），所以先贪心一下。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,h;

#define MAXN 2010

struct dwarf

{

	int a,b;

}s[MAXN];

bool cmp(dwarf x,dwarf y){return x.a + x.b < y.a + y.b;}

int f[MAXN][MAXN];

int sufh[MAXN]; 

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d%d",&s[i].a,&s[i].b);

	}

	scanf("%d",&h);

	sort(s + 1,s + 1 + n,cmp);

	for(int i = n;i >= 1;--i)sufh[i] = sufh[i + 1] + s[i].a;

	memset(f,0xc0,sizeof(f));

	f[0][0] = 0;

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

	{

		for(int j = i;j >= 0;--j)

		{

			f[i][j] = f[i - 1][j] + s[i].a;

			if(j >= 1 && f[i - 1][j - 1] + s[i].a + s[i].b + sufh[i + 1] >= h)

			{

				f[i][j] = max(f[i][j],f[i - 1][j - 1]);

			}

		}

	}

	for(int i = n;i >= 0;--i)

	{

		if(f[n][i] >= 0)

		{

			cout << i << endl;

			break;

		}

	}

	return 0;

}