【传送门：BZOJ3174】
简要题意：
给出n个人，给出每个人的身高a[i]，手长b[i]，他们被困在了高为h的井里，他们可以搭人梯，人梯的长度为（假设当前人梯的人的编号为1到k的话）
a[1]+a[2]+a[3]+...+a[k]+h[k]，如果人梯长度大于h，则第k个人能逃走，逃走了之后就不会再回来了
求出最多能逃走多少个人
题解：
为一位神犇打call[打开异世界的大门]
总的来说假设有两个人，x，y
如果x.a+x.b<y.a+y.b的话，那么x肯定会比y先逃跑
大致可以理解为逃跑能力强的人先留下
这样用DP来做贪心，f[i]表示剩下i个人时能够建成的最高人梯长度（不算手长）
参考代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; struct node { int a,b; }s[2100]; int cmp(const void *xx,const void *yy) { node n1=*(node *)xx; node n2=*(node *)yy; if(n1.a+n1.b<n2.a+n2.b) return -1; if(n1.a+n1.b>n2.a+n2.b) return 1; return 0; } int f[2100]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&s[i].a,&s[i].b); int h; scanf("%d",&h); qsort(s+1,n,sizeof(node),cmp); memset(f,-1,sizeof(f)); f[0]=0; for(int i=1;i<=n;i++) f[0]+=s[i].a; int t=0; for(int i=1;i<=n;i++) { for(int j=t;j>=0;j--) { if(f[j]+s[i].b>=h) f[j+1]=max(f[j+1],f[j]-s[i].a); if(f[t+1]>=0) t++; } } printf("%d ",t); return 0; }