问题描述
一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。
对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。
如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。
输入格式
第一行一个整数N， 表示矮人的个数，接下来N行每一行两个整数Ai和Bi，最后一行是H。（Ai，Bi，H<=10^5）
输出格式
一个整数表示对多可以逃跑多少小矮人
样例输入
2
20 10
5 5
30
样例输出
2
解析
一个直观的思路是让逃生能力弱的先逃走。对于一个矮人，如果他身体很长而手很短，那么用它辅助其他人逃跑是更优的；反过来，如果他手长身短，那么让他直接逃走不会更差。所以，我们先把两个评判标准相加后从小到大排序。但这样做并不能保证是对的，我们在排好序之后要进行DP，设\(f[i]\)表示i个人逃出去时的最大高度，那么状态转移方程为
\[f[i+1]=f[i]+1,b[i]+f[i]>=h
\]
\]
最后输出最大的i使得\(f[i]\)不等于0。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 2002
using namespace std;
const int inf=1<<30;
struct people{
int a,b;
}t[N];
int n,h,i,j,f[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
int my_comp(const people &x,const people &y)
{
return x.a+x.b<y.a+y.b;
}
int main()
{
n=read();
for(i=1;i<=n;i++) t[i].a=read(),t[i].b=read();
h=read();
sort(t+1,t+n+1,my_comp);
for(i=1;i<=n;i++){
f[i]=-inf;
f[0]+=t[i].a;
}
for(i=1;i<=n;i++){
for(j=i-1;j>=0;j--){
if(f[j]+t[i].b>=h) f[j+1]=max(f[j+1],f[j]-t[i].a);
}
}
for(i=n;i>=0;i--){
if(f[i]!=-inf){
printf("%d\n",i);
break;
}
}
return 0;
}
Tips
关键在于矮人逃生的顺序。要让逃生能力弱的先跑，可以把身高和臂长加起来从小到大排序。另外DP转移时为了避免重复更新，先枚举当前是哪个人再从后往前枚举已经跑了几个人。
没想出来是因为没有想到逃生能力弱的判定方法。以后双关键字排序可以想一想组合起来是否满足贪心。
另外，贪心+DP也是一种重要的思想。