【JZOJ100044】abcd【DP】【背包】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/100044
题目图片：
http://wx4.sinaimg.cn/mw690/0060lm7Tly1fy7h522lqej30j50dk3zl.jpg
http://wx4.sinaimg.cn/mw690/0060lm7Tly1fy7h522g0rj30jv0h3glu.jpg
http://wx1.sinaimg.cn/mw690/0060lm7Tly1fy7h5226qpj30j204vgli.jpg
给定$a,b,c,d$四个数组，求$e$，使得
$left{egin{matrix}a_ileq e_ileq b_i\ sum^{n}_{i=1}e_i imes c_i=0\ max{sum^{n}_{i=1}e_i imes d_i}end{matrix} ight.$

求$max{sum^{n}_{i=1}e_i imes d_i}$。

---

思路：

看得出是一个多重背包吗?
对于第$i$个“物品”：

• 价值$d_i$
• 重量$c_i$
• $a_ileq$个数$leq b_i$

首先，由于必须选择至少$a_i$个物品$i$，所以就直接取走$a_i$个物品$i$。剩余$b_i-a_i$个物品$i$。
那么就是一个模板的多重背包了。
用二进制拆分变成$01$背包，然后求出$f[m]$，最终答案就是$f[m]+$必须选的部分。

---

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=200010;
int n,m,s,a,b,c,d,ans,sum,w[N],v[N],f[N];

int main()
{
	scanf("%d",&s);
	while (s--)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		sum+=a*d;  //必须选
		m-=a*c;
		b-=a;
		for (int i=1;i<=b;i*=2)  //二进制拆分
		{
			w[++n]=i*c;
			v[n]=i*d;
			b-=i;
		}
		if(b) w[++n]=b*c,v[n]=b*d;
	}
	memset(f,0x80,sizeof(f));
	f[0]=0;
	for (int i=1;i<=n;i++)  //背包
		for (int j=m;j>=w[i];j--)
			f[j]=max(f[j],f[j-w[i]]+v[i]);
	printf("%d
",f[m]+sum);
	return 0;
}