求助!求神犇帮助壮大我背包

P1478 陶陶摘苹果(升级版)

entity @ 2019-11-13 21:30:51

#include<iostream>
#include<algorithm> 
using namespace std;
/*
->95

*/
struct node{
    int h,c;
}data[5001]={};
int f[5001][1001]={};
bool cmp(node a,node b){
    if(a.h==b.h) return a.c<b.c;
    else return a.h<b.h;
}
int n,s,a,b;
int main(){
    cin>>n>>s>>a>>b;
    for(int i=1;i<=n;i++) cin>>data[i].h>>data[i].c;
    a+=b;
    sort(data+1,data+1+n,cmp);
    for(int i=1;i<=n;i++){
        for(int j=s;j>=data[i].c;j--){
            if(a>=data[i].h) f[i][j]=max(f[i][j],f[i-1][j-data[i].c]+1);
            else f[i][j]=f[i-1][j];
        }
    }
    cout<<f[n][s];
    return 0;
}

这段代码WA了两个点……


by 赫敏·东方延绪 @ 2019-11-13 21:37:26

@entity 我用的是贪心,A了


|