80pts求助
查看原帖
80pts求助
526507
klm3533690023楼主2023/10/20 13:15
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int n,ans,st,ed,c,w1[10005],v1[10005],p1[10005];
int cnt,w[100005],v[100005],p[100005],dp[100005];
int main(){
	cin>>s1>>s2>>n;
	st=((s1[0]^48))*60+((s1[2]^48)*10+(s1[3]^48));
	ed=((s2[0]^48))*60+((s2[2]^48)*10+(s2[3]^48));
	c=ed-st;
	for(int i=1;i<=n;i++){
		scanf("%d",&v1[i]);
		scanf("%d",&w1[i]);
		scanf("%d",&p1[i]);
		if(p1[i]==0) p1[i]=c/v1[i];
	}
	for(int i=1;i<=n;i++){
		int j=1;
		p1[i]-=j;
		while(p1[i]>=0){
			cnt++;
			w[cnt]=w1[i]*j;
			v[cnt]=v1[i]*j;
			j*=2;
			p1[i]-=j;
		}
		p1[i]+=j;
		if(p1[i]>0){
			cnt++;
			w[cnt]=w1[i]*p1[i];
			v[cnt]=v1[i]*p1[i];
		}
	}
	for(int i=1;i<=cnt;i++)
		for(int j=c;j>=v[i];j--)
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	for(int i=1;i<=c;i++) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}
2023/10/20 13:15
加载中...