求助
  • 板块CF730J Bottles
  • 楼主OLE_OIer
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/4/1 17:07
  • 上次更新2023/10/28 04:56:01
查看原帖
求助
481855
OLE_OIer楼主2022/4/1 17:07

代码调不出来……求大佬帮忙找一下bug。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct bot{
	int p,q;
};
bool cmp(bot x,bot y){
	return x.q>y.q;
}
bot a[110];
int n,w;
int ans,tot;
int cnt=0;
int dp[110];
signed main(){
	memset(dp,128,sizeof(dp));
	dp[0]=1;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].p;
		tot+=a[i].p;
	}
	for(int i=1;i<=n;++i) cin>>a[i].q;
	sort(a+1,a+n+1,cmp);
	while(w<tot) w+=a[++cnt].q;
	cout<<cnt<<" ";
	for(int i=1;i<=n;++i){
		for(int j=1;j<=cnt;++j){
			for(int k=w;k>=a[i].q;--k)
				dp[k]=max(dp[k],dp[k-a[i].q]+a[k].p);
		}
	}
	for(int i=tot;i<=w;++i) ans=max(ans,dp[i]);
	cout<<tot-ans;
	return 0;
}
2022/4/1 17:07
加载中...