92分help
查看原帖
92分help
957205
Frommyvalleyuphard楼主2025/6/25 10:44
#include<bits/stdc++.h>
using namespace std;
long long t[300],u[300],dp[22000],ans[300];
long long nt[6000],nu[6000],bac[6000],p=0,j=0,j2=0;
int main(){
	long long k,s,v=0;
	cin>>k;
	for(long long l=0;l<k;l++){
		cin>>t[l];
	}
	for(long long l=0;l<k;l++){
		cin>>u[l];
	}
	cin>>s;
	for(long long l=0;l<k;l++){
		long long z=1;
		while(u[l]>=z){
			u[l]-=z,nu[p]=z,nt[p]=t[l],bac[p]=l,p++,z*=2;
		}
		if(u[l]!=0){
			nu[p]=u[l],nt[p]=t[l],bac[p]=l,p++;
		}
	}
	for(long long m=0;m<=s;m++){
		dp[m]=1145141919810;
	}
	dp[0]=0;
	for(long long l=0;l<p;l++){
		for(long long m=s;m>=nt[l]*nu[l];m--){
			dp[m]=min(dp[m],dp[m-nt[l]*nu[l]]+nu[l]);
		}
	}
	cout<<dp[s]<<endl;
	v=s;
	for(long long l=0;l<dp[s];l++){
		for(long long m=0;m<k;m++){
			if(v>=t[m] && dp[v-t[m]]==dp[v]-1){
				ans[m]++,v-=t[m];
			}
		}
	}
	for(long long l=0;l<k;l++){
		cout<<ans[l]<<' ';
	}
}
2025/6/25 10:44
加载中...