40pt,玄关
  • 板块P1833 樱花
  • 楼主JURUOzhao
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/5 11:33
  • 上次更新2024/10/5 12:40:29
查看原帖
40pt,玄关
969039
JURUOzhao楼主2024/10/5 11:33
#include<bits/stdc++.h>
using namespace std;
int c[200050],p[100005],t[100005],n,tt,t11,t12,t21,t22;
int cnt[100005],dp[1000010];
char cc;
struct nd{
	int w,tim;
};
vector<nd>v[1000005];
int main(){
	cin>>t11>>cc>>t12>>t21>>cc>>t22;
	cin>>n;
	tt=(t21-t11+24)%24*60+t22-t12;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>c[i]>>p[i];
	}
	for(int i=1;i<=n;i++){
		if(p[i]){
		int sum=0;
		int base=1;
		while(base<=p[i]){
			v[i].push_back({base*c[i],base*t[i]});
			base<<=1;
			sum++;
		}
		v[i].push_back({p[i]-(base/2)*c[i],(p[i]-(base/2))*t[i]});
		cnt[i]=sum;
		}
	}
	dp[0]=0;
	for(int i=1;i<=n;i++){
		if(p[i]){
			for(auto x:v[i]){
				for(int j=tt;j>=x.tim;j--){
				dp[j]=max(dp[j],dp[j-x.tim]+x.w);
				}
			}
			
		}
		else{
			for(int j=t[i];j<=tt;j++){
			dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
			}
		}
	}
	cout<<dp[tt];
	return 0;
}
2024/10/5 11:33
加载中...