40分,求调
  • 板块P1833 樱花
  • 楼主Ly120816
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/29 16:28
  • 上次更新2024/7/29 16:30:35
查看原帖
40分,求调
1389739
Ly120816楼主2024/7/29 16:28
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 114514;
const int M = 1e3 + 114514;
int tsh,tsm,teh,tem,n,V; 
int c[N],v[N],p[N],dp[M];
void ly(int c,int v)
{
	for(int j = V;j >= c;j--)
	{
		dp[j] = max(dp[j],dp[j - c] + v);
	}
} 
void wq(int c,int v)
{
	for(int j = c;j <= V;j++)
	{
		dp[j] = max(dp[j],dp[j - c] + v);
	}
} 
void dc(int c,int v,int a)
{
	if(V <= a * c || a == 0)
	{
		wq(c,v);
	}
	else
	{
		int k = 1;
		while(k < a)
		{
			ly(k * c,k * c);
			a -= k;
			k <<= 1;
		}
		if(a > 0)
		{
			ly(a * c,a * v);
		}
	}
}
int main()
{
	scanf("%d:%d %d:%d %d",&tsh,&tsm,&teh,&tem,&n);
	V = (teh - tsh) * 60 + tem - tsm;
	for(int i = 1;i <= n;i++)
	{
		scanf("%d%d%d",&c[i],&v[i],&p[i]);
	}
	for(int i = 1;i <= n;i++)
	{
		dc(c[i],v[i],p[i]);
	}
	printf("%d\n",dp[V]);
	return 0;
}
2024/7/29 16:28
加载中...