BZOJ3174:[Tjoi2013]拯救小矮人 贪心+dp

思路:

假设在能逃出相同多数目的小矮人的情况下,我们更愿意让逃生能力更强的小矮人留到最后.

逃生能力就是指\(a_i+b_i\),也即在下面垫的总高度确定时更容易达到更高的高度.

这样我们就有了一个贪心选择顺序,我们设\(f[i]\)表示逃生了\(i\)个小矮人时下面垫的总高度的最大值,并依据这个判定能否再逃出一人即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 2010
struct Case{int a,b;bool operator<(const Case&B)const{return a+b<B.a+B.b;}}S[N];
 
int f[N];
int main(){
    int n,m;scanf("%d",&n);register int i,j;for(i=1;i<=n;++i)scanf("%d%d",&S[i].a,&S[i].b);
    sort(S+1,S+n+1);
    scanf("%d",&m);
    memset(f,-1,sizeof f);for(f[0]=0,i=1;i<=n;++i)f[0]+=S[i].a;
    int ans=0;
    for(i=1;i<=n;++i){
        for(j=ans;j>=0;--j){
            if(f[j]+S[i].b>=m)f[j+1]=max(f[j+1],f[j]-S[i].a);
             
        }if(f[ans+1]>=0)++ans;
    }
    printf("%d\n",ans);
    return 0;
}