题解【P1833 樱花】

题目

有 \(n\) 棵樱花，有三种：

只能看一次
最多看 \(A_i\) 遍
能无限看

看每棵樱花都需要一定时间 \(T_i\)，求从 \(T_s\) 开始，到 \(T_e\) 结束（时间）最多能看多少樱花。

题解

混合背包板子，01 背包相当于 \(1\) 个物品的多重背包，完全背包相当于 inf 个物品的多重背包，都用多重背包即可。

要二进制拆分优化，注意多重背包的 inf 不能开太大，不然会 RE .

#include<iostream>

#include<ctime>

#include<queue>

#include<stack>

#include<cmath>

#include<iterator>

#include<cctype>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

namespace Main

{

	const int N=1000005,INF=0x3f3f3f3f;

	int t,T,n,c[N],v[N],dp[N];

	struct node{int T,C,P;}a[N];

	void split() // 二进制拆分

	{

		for (int i=0;i<n;i++)

		{

			int z=1;

			while (a[i].P) // index from 0 => index from 1

			{

				c[++T]=z*a[i].T; v[T]=z*a[i].C; a[i].P-=z; z<<=1;

				if (a[i].P<z){c[++T]=a[i].T*a[i].P; v[T]=a[i].C*a[i].P; break;}

			}

		}

	}

	void zbag() // 01 背包

	{

		for (int i=1;i<=T;i++)

			for (int j=t;j>=c[i];j--)

				dp[j]=max(dp[j],dp[j-c[i]]+v[i]);

	}

	inline void mbag(){split(); zbag();} // 多重背包

	int main()

	{

		int hh1,mm1,hh2,mm2,Ts,Te;

		scanf("%d:%d %d:%d %d",&hh1,&mm1,&hh2,&mm2,&n);

		Ts=hh1*60+mm1; Te=hh2*60+mm2; t=Te-Ts;

		for (int i=0;i<n;i++)

		{

			scanf("%d%d%d",&a[i].T,&a[i].C,&a[i].P);

			if (!a[i].P) a[i].P=INF;

		} mbag(); printf("%d",dp[t]);

		return 0;

	}

}

int main(){return Main::main();}

巴特西

题解【P1833 樱花】

题目

题解

最新文章

热门文章