0分求条
  • 板块P1833 樱花
  • 楼主zhuyanxi
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/8 17:11
  • 上次更新2024/8/8 18:29:20
查看原帖
0分求条
763805
zhuyanxi楼主2024/8/8 17:11
#include <bits/stdc++.h>
using namespace std;
struct S{
	int v, p, k;
};
int n, w;
int v[10008], p[10008], a[10008];
vector<S> b;
int main()
{
	int h1, m1, h2, m2;
	scanf("%d:%d %d:%d", &h1, &m1, &h2, &m2);
	w = (h2-h1)*60+(m2-m1);
	cin >>n;
	for(int i=1; i<=n; i++){
		scanf("%d %d %d", &v[i], &p[i], &a[i]);
		if(a[i]==0){
			S tmp;
			tmp.v = v[i];
			tmp.p = p[i];
			tmp.k = 0;
			b.push_back(tmp);
		}
		else{
			int d = 1, tot = 0;
			S tmp;
			while(1){
				tmp.v = v[i]*d;
				tmp.p = p[i]*d;
				tmp.k = 1;
				b.push_back(tmp);
				tot += d;
				d *= 2;
				if(tot>=a[i]/2){
					break;
				}
			}
			int h = a[i]-tot;
			if(h!=0){
				tmp.v = v[i]*h;
				tmp.p = p[i]*h;
				tmp.k = 1;
				b.push_back(tmp);
			}
		}
	}
	int dp[10008];
	int nn = b.size();
	for(int i=0; i<nn; i++){
		int tv = b[i].v, tp = b[i].p, tk = b[i].k;
		if(tk==0){
			for(int j=tv; j<=w; j++){
				dp[j] = max(dp[j], dp[j-tv]+tp);
			}
		}
		else{
			for(int j=w; j>=tv; j--){
				dp[j] = max(dp[j], dp[j-tv]+tp);
			}
		}
	}
	int ans = 0;
	for(int i=0; i<=w; i++){
		ans = max(ans, dp[i]);
	}
	printf("%d\n", ans);
	return 0;
}
2024/8/8 17:11
加载中...