[文章目录]
Description
一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。n<=2000
想到一个错误贪心：二分答案：二分不能够跑出去的个数mid，将高度前mid的人先扔里，然后再将所有的人按照a+b排序，如果能出去，就累加a。直到不能够出去，返回false。
bug在于可以用不能够爬出去的人将下面的人替换。使得该答案合法。
正解是贪心+DP。
如果相邻两个都跑出去，那么a+b大的那个一定后出去。所以排序。然后dp：设f[i]表示逃出去i个后坑里剩下的最大高度。
每次用新的人更新答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,h,f[2100];
struct node
{
int a,b;
}a[2010];
bool cmp(node x,node y)
{
return x.a+x.b<y.a+y.b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].a,&a[i].b);
scanf("%d",&h);
sort(a+1,a+n+1,cmp);
int tmp=0;
memset(f,-1,sizeof f); f[0]=0;
for(int i=1;i<=n;i++)
f[0]+=a[i].a;
for(int i=1;i<=n;i++)
{
for(int j=tmp;j>=0;j--)
{
if(f[j]+a[i].b>=h)
f[j+1]=max(f[j+1],f[j]-a[i].a);
if(f[tmp+1]>=0) tmp++;
}
}
printf("%d",tmp);
return 0;
}