P2370 yyy2015c01的U盘

2020-1-17 4:34

1,140

未分类

54 字

几秒读完

链接：Miku

这是一道01背包+二分

二分的部分很普通，至于check函数，也不过是忽略掉了所以比接口还大的物品而已

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,p,s;
int dp[100000];
int w[10000];
int v[10000];
int l,r=19260817;
bool check(int k){
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i){
        if(w[i]<=k)
        for(int j=s;j>=w[i];--j){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    if(dp[s]>=p)
    return 1;
    return false;
}
int main(){
    scanf("%d%d%d",&n,&p,&s);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&w[i],&v[i]);
    }
//    cout<<43432;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)) r=mid-1;
        else
        l=mid+1;
    }
    if(l>=19260817)
    cout<<"No Solution!";
    else
    cout<<l;
    return 0;
}