[TJOI2013] 拯救小矮人- 贪心,dp

结论：矮的人比高的人先走一定不会使得答案变劣

于是我们排序后，像 0-1 背包那样依次考虑每个人走不走

#include <bits/stdc++.h>
using namespace std;

struct obj {
    int a,b;
    bool operator < (const obj &x) {
        return a+b < x.a+x.b;
    }
} a[10005];

int n,h,ans;
int f[2005][2005];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b;
    sort(a+1,a+n+1);
    cin>>h;
    memset(f,0xff,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++) f[0][0]+=a[i].a;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            f[i][j]=f[i-1][j];
            if(j && f[i-1][j-1]+a[i].b >= h) f[i][j]=max(f[i][j],f[i-1][j-1]-a[i].a);
            if(f[i][j]>=0 && j>ans) ans=j;
        }
    }
    cout<<ans<<endl;
}

[TJOI2013] 拯救小矮人- 贪心,dp

原文：https://www.cnblogs.com/mollnn/p/12254996.html