题解：P1782 旅行商的背包
uiii_
·
·
题解
写篇题解纪念一下本苣蒻不看题解标签做出来的第一道蓝题。
思路
题意已经十分明显了。这是一道混合背包问题。
我们可以把物品分成两类——第一类普通物品，第二类奇货。
第一类
多重背包的板子。
看一眼数据范围直接暴力肯定会超时。需要进行优化。
多重背包的优化有二进制拆分及单调队列两种方法。这里我选用了二进制拆分。
二进制拆分顾名思义就是把 k 个物品 i 拆分成 1、2、4……个，最后可以变为01背包。具体讲解可以看看 这个 。
我的代码使用的是边 dp 边拆分的方法。也可以先拆分预处理数组再进行 dp 运算。
第二类
可以看作分组背包。每个奇货为一组。组内物品体积为 $0$ ~ $C$，价值使用题目所给公式计算。
## 一些细节
十年 oi 一场空，不开 `long long` 见祖宗。
注意奇货的体积要从 $0$ 开始枚举。不难发现体积 $x$ 为 $0$ 时仍有价值为 $c$。
## Code
```cpp
#include<bits/stdc++.h>
#define lg long long
using namespace std;
lg n,m,C,v[10010],w[10010],p[10010],a,b,c,d[10010],ans;
int main(){
scanf("%lld%lld%lld",&n,&m,&C);
for(lg i=1;i<=n;i++){
scanf("%lld%lld%lld",&v[i],&w[i],&p[i]);
}
for(lg i=1;i<=n;i++){
for(lg k=1;k<=p[i];k<<=1){
for(lg j=C;j>=v[i]*k;j--){
d[j]=max(d[j],d[j-v[i]*k]+w[i]*k);
}
p[i]-=k;
}
if(p[i]){
for(lg j=C;j>=v[i]*p[i];j--){
d[j]=max(d[j],d[j-v[i]*p[i]]+w[i]*p[i]);
}
}
}//多重背包
for(lg i=1;i<=m;i++){
scanf("%lld%lld%lld",&a,&b,&c);
for(lg j=C;j>=0;j--){
for(lg k=0;k<=j;k++){
d[j]=max(d[j],d[j-k]+a*k*k+b*k+c);
}
}
}//奇货
for(int i=0;i<=C;i++){
ans=max(ans,d[i]);
}
printf("%lld",ans);
return 0;
}
```