CF1862(div3)题解

F. Magic Will Save the World

题意：
每一秒钟可以生产w个水元素和f个火元素，问需要多少秒才能消灭n个怪兽(攻击时间忽略不计，w或f大于怪兽的值可以攻击，并减少相应的值，可以同时消灭多个怪兽)
思路：
枚举n个怪兽能组成的所有值(可以用01背包求出来)，定义这一部分需要水元素消灭，剩下的用火元素消灭。
复杂度： $O(N \cdot sum) $

void solve(){
	ll w,f,n;
	cin>>w>>f>>n;
	vector<int> a(n+1);
	ll sum=0;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	vector<bool> dp(sum+1);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=sum;j>=a[i];j--)dp[j]=dp[j]||dp[j-a[i]];
	}
	ll ans=INF;
	for(ll i=0;i<=sum;i++){
		if(dp[i])ans=min(ans,max((i+w-1)/w,(sum-i+f-1)/f));
	}
	cout<<ans<<"\n";
}

G. Replace With Product