40分,求助大佬
  • 板块P1833 樱花
  • 楼主MiPoint
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/8/17 14:32
  • 上次更新2023/11/4 10:20:07
查看原帖
40分,求助大佬
491194
MiPoint楼主2021/8/17 14:32

有没有大佬帮忙看看啊

#include<bits/stdc++.h>
using namespace std;

int n,m;int st1,st2,et1,et2;//n个物品,m为容量 
int w[10005],v[10005],c[10005];
int dp[1005];

int main(){
	scanf("%d:%d %d:%d",&st1,&st2,&et1,&et2);
	cin>>n;
	m=et1*60+et2-st1*60-st2;
//	cout<<n;
	int cnt=0;
	for(int i = 1;i<=n;i++){
		int wi,vi,s;//w重量,v价值 
		scanf("%d %d %d",&wi,&vi,&s);
		if(c[i]>=1){
			int k=1;//k表示二进制2的n次方	
			while(k<=s) {
				cnt++;
				w[cnt]=wi*k;
				v[cnt]=vi*k;
				c[cnt]=1;
				s-=k;
				k*=2;
			}
			if(s>0) {//处理剩下的 
				cnt++;
				w[cnt]=wi*s;
				v[cnt]=vi*s;
				c[cnt]=1;
			}
		}
		else{
			cnt++;
			w[cnt]=wi;
			v[cnt]=vi;
			c[cnt]=0;
		}
	}
	n=cnt;
	for(int i = 1;i<=n;i++){
		if(c[i]==0){
			for(int j = w[i];j<=m;j++){
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
		else{
			for(int j = m;j>=w[i];j--){
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
	}
	cout<<dp[m];
	return 0;
}
2021/8/17 14:32
加载中...