【JZOJ100044】abcd【DP】【背包】

本文主要是介绍【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$，使得
{ a i ≤ e i ≤ b i ∑ i = 1 n e i × c i = 0 m a x { ∑ i = 1 n e i × d i } \left\{\begin{matrix}a_i\leq e_i\leq b_i\\ \sum^{n}_{i=1}e_i\times c_i=0\\ max\{\sum^{n}_{i=1}e_i\times d_i\}\end{matrix}\right. ⎩⎨⎧​ai​≤ei​≤bi​∑i=1n​ei​×ci​=0max{∑i=1n​ei​×di​}​

求 m a x { ∑ i = 1 n e i × d i } max\{\sum^{n}_{i=1}e_i\times d_i\} max{∑i=1n​ei​×di​}。

---

思路：

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

• 价值$d_i$
• 重量$c_i$
• $a_i\le$个数$\le 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\n",f[m]+sum);return 0;
}

这篇关于【JZOJ100044】abcd【DP】【背包】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---