求助dalao,思路应该没问题的
查看原帖
求助dalao,思路应该没问题的
674793
luoguhandongheng楼主2022/3/27 15:17
#include <bits/stdc++.h>
using namespace std;
const int INF=999999999;
int f[10005],c[10005],p[10005],t[10005],s,n;
void input()
{
	string a,b;
	cin>>a>>b>>n;
	int flag=0;
	int x,y;
	if(a.size()==4){	
		x=(a[0]-'0')*60+(a[2]-'0')*10+(a[3]-'0'); 
	}
	if(a.size()==5){	
		x=((a[0]-'0')+(a[1]-'0'))*60+(a[3]-'0')*10+(a[4]-'0'); 
	}
	if(b.size()==4){	
		y=(b[0]-'0')*60+(b[2]-'0')*10+(b[3]-'0'); 
	}
	if(b.size()==5){	
		y=((b[0]-'0')+(b[1]-'0'))*60+(b[3]-'0')*10+(b[4]-'0'); 
	}
	s=y-x;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i]>>c[i]>>p[i]; 
		if(p[i]==0)	p[i]=INF;
	}
}
void dp()
{ 
	for(int i=1;i<=n;i++)
	{		
		if(p[i]==INF)//如果p[i]是无限的,就是一个完全背包。 
		{
			for(int j=t[i];j<=s;j++)
			{
				f[j]=max(f[j],f[j-t[i]]+c[i]);		
			}
		}
		else if(p[i]>1) //如果不是无限的,就是一个多重背包 
		{	
			for(int k=0;k<=p[i];k++)
				for(int j=s;j>=t[i];j--)
				{
						if(k*p[i]<=j)
							f[j]=max(f[j],c[i]*k+f[abs(j-t[i]*k)]);
						else break;
				}
		}
		else//还不是就是01背包了 
		{
			for(int j=s;j>=1;j--)
			{
				f[j]=max(f[j],c[i]+f[j-t[i]]);  
			}
		}	
	}
}
int main()
{
	input();
	dp();
	cout<<f[s];
	return 0;
}

2022/3/27 15:17
加载中...