80分求调
  • 板块P1833 樱花
  • 楼主doooge
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/31 09:03
  • 上次更新2024/7/31 10:50:13
查看原帖
80分求调
1286553
doooge楼主2024/7/31 09:03
#include <bits/stdc++.h>
using namespace std;
int dp[100010],ww[5010],vv[5010];
int main()
{
	string s,s2;
	int n,m,num = 0,num2 = 0,num3 = 0,num4 = 0;
	cin >> s >> s2 >> n;
	int pos = s.find(":");
	for (int i = 0 ; i < pos ; i++) num = num * 10 + s[i] - '0';
	for (int i = pos + 1 ; i < s.size() ; i++) num2 = num2 * 10 + s[i] - '0';
	int pos2 = s2.find(":");
	for (int i = 0 ; i < pos2 ; i++) num3 = num3 * 10 + s2[i] - '0';
	for (int i = pos2 + 1 ; i < s2.size() ; i++) num4 = num4 * 10 + s2[i] - '0';
	if (num3 * 60 + num4 < num * 60 + num2) m += 1440;
	m = num3 * 60 + num4 - num * 60 - num2;
	int cnt = 0;
	for (int i = 1 ; i <= n ; i++)
	{
		int w,v,s;
		cin >> w >> v >> s;
		if (s == 0) s = m / w;
		for (int j = 1 ; j <= s ; j *= 2)
		{
			cnt++;
			ww[cnt] = w * j;
			vv[cnt] = v * j;
			s -= j;
		}
		if (s > 0)
		{
			cnt++;
			ww[cnt] = w * s;
			vv[cnt] = v * s;
		}
	}
	for (int i = 1 ; i <= cnt ; i++)
	{
		for (int j = m ; j >= ww[i] ; j--)
		{
			dp[j] = max(dp[j] , dp[j - ww[i]] + vv[i]);
		}
	}
	cout << dp[m] << endl;
	return 0;
}
2024/7/31 09:03
加载中...