混合背包WA得莫名其妙
查看原帖
混合背包WA得莫名其妙
858608
BreadCakeCheese楼主2024/7/25 20:21

好吧其实也没有莫名其妙,就是小蒟蒻太菜了

混合背包模板WA了最后两个点

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct node{
	int w,v,p;
}bg[N]; 
int n,cnt=0,t;
long long dp[1001];
int change(string s){
	if(s[1]==':'){
		if(s.size()==3) return (s[0]-'0')*60+(s[2]-'0');
		else return (s[0]-'0')*60+(s[2]-'0')*10+(s[3]-'0'); 
	}else{
		if(s.size()==4) return ((s[0]-'0')*10+(s[1]-'0'))*60+(s[3]-'0');
		else return ((s[0]-'0')*10+(s[1]-'0'))*60+(s[2]-'0')*10+(s[3]-'0');
	}
}
int main(){
	string s;
	cin>>s;
	int t1=change(s);
	cin>>s;
	int t2=change(s);
	t=t2-t1;
	cin>>n;
	for(int i=1;i<=n;i++){
		int w,v,p;
		cin>>w>>v>>p;
		if(p==1||p==0){ // 01背包 || 完全背包 
			cnt++;
			bg[cnt].w=w;
			bg[cnt].v=v;
			bg[cnt].p=p;
		}else{ // 多重背包 
			int k=1;
			while(k<=p){
				cnt++;
				bg[cnt].w=w*k;
				bg[cnt].v=v*k;
				bg[cnt].p=1;
				p-=k;
				k*=2;
			}
			if(p>0){
				cnt++;
				bg[cnt].w=w*p;
				bg[cnt].v=v*p;
				bg[cnt].p=1;
			}
		}
	}
	for(int i=1;i<=cnt;i++){
		if(bg[i].p==1){
			for(int j=t;j>=bg[i].w;j--){
				dp[j]=max(dp[j],dp[j-bg[i].w]+bg[i].v);
			}
		}else{
			for(int j=bg[i].w;j<=t;j++){
				dp[j]=max(dp[j],dp[j-bg[i].w]+bg[i].v);
			}
		}
	}
	cout<<dp[t]<<endl;
	return 0;
}
2024/7/25 20:21
加载中...