sxczf's Blog

if (f[i]+Bx>=H)//第x人可以逃跑
f[i+1]=max(f[i+1],f[i]-Ax);//答案更新

但是显然需要先根据贪心思想进行排序……

根据Ai+Bi从小到大排序……

不要问我为什么……

自己yy……

假设陷阱高度为50,有3个人，

A1=20,B1=20;

A2=40,B2=9;

A3=1,B3=50;

显然应该先让第一个人跑掉，然后是第二个人，然后第三个人

让Ai+Bi小的先跑掉……

Ai+Bi越大，底下垫的人需要的高度就越小，可以先让更多的人跑……

代码：

/**************************************************************
    Problem: 3174
    User: sxczf
    Language: C++
    Result: Accepted
    Time:16 ms
    Memory:828 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
using namespace std;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
int b,c,d,e,f[2005],g,h,i,j,k,l,m,n;
struct czf{int a,b;}a[2005];
inline bool cmp(czf a,czf b){return a.a+a.b<b.a+b.b;}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d%d",&a[i].a,&a[i].b);
    sort(a+1,a+1+n,cmp);
    scanf("%d",&m);
    for(i=1;i<=n;i++)f[0]+=a[i].a;
    for(i=1;i<=n;i++)f[i]=-1;
    h=0;
    for(i=1;i<=n;i++){
        for(j=h;j>=0;j--)
        if (f[j]+a[i].b>=m){
            if (f[j]-a[i].a>f[j+1])
            f[j+1]=f[j]-a[i].a;
        }
        if (f[h+1]>=0)h++;
    }
    printf("%d",h);
    return 0;
}