70分求助
查看原帖
70分求助
400148
清木楼主2022/9/14 17:08
#include<bits/stdc++.h>
using namespace std;
int cnt,x,y,n,p,s,flag,anss=1e9;
int w[1005],v[1005],ans[1000005],f[1000005];
int main(){
	freopen("P2370_5.in","r",stdin);
	cin>>n>>p>>s;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
//		if(x>s){
//			continue;
//		} 
		w[++cnt]=x;
		v[++cnt]=y;
	}
	for(int i=1;i<=cnt;i++){
		for(int j=s;j>=w[i];j--){
			if(f[j-w[i]]+v[i]>f[j]){
				f[j]=f[j-w[i]]+v[i];
				ans[j]=max(ans[j-w[i]],w[i]);	
			}
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	for(int i=s;i>=0;i--){
		if(f[i]<p){
			break;
			cout<<endl;
		}
		else{
			anss=min(anss,ans[i]);
			flag=1;
		}
	}
	if(flag){
		cout<<anss;
	}
	else{
		cout<<"No Solution!";
	}
//	cout<<f[505];
	return 0;
}

记录路径70分

2022/9/14 17:08
加载中...