题解 P6433 【「EZEC-1」出题】
Mars_Dingdang
2020-10-08 16:47:07
本题是一道背包 dp 的好题，可以对某些物品的权值进行增益操作。
## 题目大意
已知你有 $n$ 道毒瘤题，已经出好了题面，但数据还没出好。你还剩下 $m$ 的时间，每道题的毒瘤程度为 $a_{i}$，出数据的时间是 $x_{i}$，你有 $k$ 个老师，每个老师可以把一道题的毒瘤程度翻倍（每道题目最多被翻倍一次）。你的父母由于坚决反对你出公开赛，抢走了你的一道题，现在老师和父母的行动你都可以控制，但每位老师和父母的行为必须执行，请问你要怎么做，才能使出的题毒瘤程度之和最大。
简化：有 $n$ 个物品，每个物品价值为 $w_i$，所占空间为 $t_i$，背包容量为 $m$，有 $k$ 次物品价值翻倍的机会（每件物品价值只能翻倍一次），必须从中取走一件，问背包所装物品的最大价值。
## 大体思路
### 【贪心】
本题的贪心策略是：如果背包无论如何都装不满，即 $\sum_{i=1}^n v_i\le m$，则只需要放弃权值最小的一道题，然后从大到小排序，保证权值较大的 $k$ 道题翻倍。这样所得的权值总和是 $\sum_{i=1}^n w_i+\max\sum_{i=1}^k w_i$ 显然最大。代码如下：
```cpp
n=read(),m=read(),k=read();//顶上还有一些快读函数
for(re int i=1;i<=n;i++){
w[i]=read();
v[i]=read();
sum+=v[i];
}//输入
if(sum<=m){//装不满
sort(w+1,w+n+1,greater<int>());//从大到小排序
for(re int i=1;i<=k;i++){
ans+=(w[i]<<1);
}//翻倍
for(re int i=k+1;i<=n-1;i++){
ans+=w[i];
}
cout<<ans;//输出
return 0;
}
```
### 【背包 DP】
用 $f(i,j)$ 表示体积为 $i$，权值翻倍 $j$ 次后的最大权值和。注意坑：放弃的题目可以不用出数据，因此不用管父母的操作。
状态转移方程：$f(i,j)=\max\left\{f(i,j),f(i-v_i,j)+w_i,f(i-v_i,j-1)+2w_i\right\},ans=\max(ans,f(i,j)$。
把 $j=0$ 拎出来单独弄即可。代码如下：
```cpp
for(re int l=1;l<=n;l++){
for(re int i=m;i>=v[l];i--){
for(re int j=min(l,k);j>=1;j--){
f[i][j]=max(f[i][j],max(f[i-v[l]][j]+w[l],f[i-v[l]][j-1]+(w[l]<<1)));
ans=max(ans,f[i][j]);
}
f[i][0]=max(f[i][0],f[i-v[l]][0]+w[l]);
ans=max(ans,f[i][0]);
}
}
cout<<ans;
```