Description
一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。解题报告: 用时:1h20min,3WA 这题一开始写了个错的，首先显然是可以按\(ai+bi\)排序，因为能力强的要放在最后逃跑，然后简单的认为:能出去的就出去，不能出去的先丢入堆中，如果当前的矮人逃不出去，那么就用堆中的元素帮他出去，但是显然是错的....然后发现这个东西需要决策.然后想到DP，天真以为\(f[i]=f[j]+1\),如果\(j-i\)中的矮人堆起来可以帮\(i\)逃出去,然而还是不对，参考题解的状态.\(f[i]\)为逃出\(i\)人，剩下的人\(ai\)和的最大值.然后想到背包，\(f[j+1]=f[j]-a[i]\)，最后找到合法的最大\(j\)即可
#include#include #include #include #include #include #include #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;const int N=2005;struct node{ int x,y; bool operator <(const node &pr)const{ return x+y>pr.x+pr.y; }}a[N];int f[N];void work(){ int n,H; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); sort(a+1,a+n+1);scanf("%d",&H); int ans=0; memset(f,-1,sizeof(f));f[0]=0; for(int i=1;i<=n;i++)f[0]+=a[i].x; for(int i=n;i>=1;i--){ for(int j=ans;j>=0;j--) if(f[j]+a[i].y>=H) f[j+1]=Max(f[j+1],f[j]-a[i].x); if(f[ans+1]>=0)ans++; } printf("%d\n",ans);}int main(){ work(); return 0;}