50分求解,加了优化的
查看原帖
50分求解,加了优化的
715948
small_lemon_qwq楼主2023/3/5 13:01
#include<bits/stdc++.h>
using namespace std;
int dp[100005],n,v,C[100005],V[100005],cnt,w[100005];
int main(){
	int a,b,c,d;
	scanf("%d:%d%d:%d",&a,&b,&c,&d);
	v=60*c+d-60*a-b;
	cin>>n;
	for(int i=1;i<=n;i++){
		int cc,ww,vv;
		scanf("%d%d%d",&vv,&cc,&ww);
		w[i]=(ww!=0);
		if(ww!=0){
			for(int j=1;j<=ww;j=j<<1){
				cnt++;
				C[cnt]=j*cc;
				V[cnt]=j*vv;
				ww-=j;
			}
			if(ww){
				cnt++;
				C[cnt]=ww*cc;
				V[cnt]=ww*vv; 
			}
		}else{
		    cnt++;
			V[i]=vv;
			C[i]=cc;
		}
	}
	for(int i=1;i<=cnt;i++){
		if(w[i]!=0){
			for(int k=v;k>=V[i];k--){
				dp[k]=max(dp[k],C[i]+dp[k-V[i]]);
			}
		}else{
			for(int k=V[i];k<=v;k++){
				dp[k]=max(dp[k],C[i]+dp[k-V[i]]);
			}
		}
		
	}
	printf("%d",dp[v]);
	return 0;
}
2023/3/5 13:01
加载中...