混合背包求助QAQ
  • 板块P1833 樱花
  • 楼主MaoMaoNB
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/10/8 19:05
  • 上次更新2023/11/4 04:20:15
查看原帖
混合背包求助QAQ
290406
MaoMaoNB楼主2021/10/8 19:05

不知道为什么蛙了两个点

这是代码

#include<bits/stdc++.h>
using namespace std;
int n,V,t1,t2,t3,t4;
int c,p,w,f[1010]={};
int main(){
	scanf("%d:%d",&t1,&t2);
	scanf("%d:%d",&t3,&t4);
	cin>>n;
	V=(t3-t1)*60+t4-t2;
	for(int i=1;i<=n;i++){
		cin>>c>>w>>p;
		if(p==1){
			for(int j=V;j>=c;j--)
			 f[j]=max(f[j],f[j-c]+w);
		}
		if(p==0){
			for(int j=c;j<=V;j++)
			 f[j]=max(f[j],f[j-c]+w);
		}
		else{
			int num=p;
			for(int k=1;num>0;k<<=1){
				if(k>num)k=num;
				num-=k;
				for(int j=V;j>=c*k;j--)
				 f[j]=max(f[j],f[j-c*k]+w*k);
			}
		}
	};
	cout<<f[V];
	return 0;
}

我的二进制优化可能跟大佬们的习惯不大一样,但是跑多重背包模板还是过了的

给出WA的数据,为什么会WA啊QAQ

输入:
6:00 6:59 10
7 19 2
5 3 0
2 37 1
2 15 0
3 26 0
6 18 4
6 19 4
7 7 3
5 19 1
3 56 2

输出:
591

2021/10/8 19:05
加载中...