[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

最新文章

热门文章