80分求调
  • 板块P1833 樱花
  • 楼主Arrtan_73
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/3/9 20:32
  • 上次更新2023/10/23 22:05:15
查看原帖
80分求调
736527
Arrtan_73楼主2023/3/9 20:32

#include <bits/stdc++.h>
using namespace std;
string a, b;
long  n, m, c[10005], w[10005], f[20000], u[10005], v[10000005], g[10000005], top = 0;

int main() {
	int h1, h2, min1, min2;
	cin >> a >> b >> n;
	h1 = b[0] - '0';
	h2 = a[0] - '0';
	min1 = (b[2] - '0') * 10 + (b[3] - '0');
	min2 = (a[2] - '0') * 10 + (a[3] - '0');
	m = (h1 - h2 ) * 60 + min1 - min2;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> c[i] >> u[i];
	for (int i = 1; i <= n; i++) {
		int data = 1;
		if (u[i] == 0)
			u[i] = 1000000;
		while (u[i] != 0) {
			v[++top] = w[i] * data;
			g[top] = c[i] * data;
			u[i] -= data;
			data *= 2;
			if (u[i] < data) {
				v[++top] = w[i] * u[i];
				g[top] = c[i] * u[i];
				break;
			}
		}
	}
	for (int i = 1; i <= top; i++)
		for (int j = m; j >= v[i]; j--)
			f[j] = max(f[j], f[j - v[i]] + g[i]);
	cout << f[m];
	return 0;
}
2023/3/9 20:32
加载中...