题解 P1616 【疯狂的采药】
Mutsumi_0114
2018-01-26 13:09:00
来做这题的人应该都是看过 [【P1048】采药](https://www.luogu.org/problemnew/show/P1048) 的，在 <采药> 中，每种草药只允许 采一次 。
以下一大段为<采药>思路回顾，可适当跳过
------------
我们将采 第$i$种草药 所需的 时间 设为 $t[i]$ ， 价值 设为 $p[i]$ 。
如果有一个数组 $f[i][j]$ 来表示 从前往后 到第$i$种草药 (当然前面可能有草药不采) ，花费了 最多 $j$时间 (意思是可能花费了少于$j$时间) 时，能采到草药的 最大 价值，那它的状态转移方程是怎样的呢？
到第$i$种草药时有两种情况：采与不采。
若不采这种草药，则 时间花费没有增多 ，经过的 草药种数增加了$1$ ， 采到草药价格不变 ，所以
$$f[i][j]=f[i-1][j]$$
若采这种草药，则 时间花费增加了$t[i]$ ， 种数增加$1$ ， 采到草药价格增加了$p[i]$ ，所以
$$f[i][j]=f[i-1][j-t[i]]+p[i]$$
我们当然要使$f[i][j]$ 尽可能大 ，即有
$$f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+p[i])$$
```
-----------
|C| | | |B|
-----------
| | | | |A|
-----------
```
通过状态转移方程可以发现若 要求上图$f$数组中$A$的值，必须先求出$A$上方的$B$，以及$A$上方左边某处的$C$ 。
所以可确定递推顺序为 从左到右，从上到下
<采药> $C++$ 代码：
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int i,j,T,M,t[101],p[101],f[101][1001];
int main()
{
scanf("%d%d",&T,&M);
for(i=1;i<=M;i++)
scanf("%d%d",&t[i],&p[i]);
for(i=1;i<=M;i++)
{
for(j=0;j<t[i];j++)
f[i][j]=f[i-1][j];//针对上面的左边为数组越界的位置
for(j=t[i];j<=T;j++)
f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+p[i]);//递推
}
printf("%d",f[M][T]);
return 0;
}
```
这显然是一个 二维 的$dp$，其实我们可以将它 压缩至一维 。
若要压缩至一维，我们可以 将药的种类$i$省略 ，只开一个一维数组， 用后面算的值覆盖掉前面算的值 。
已经说过在二维$dp$中计算$A$所需要的数， 转到一维后，其实就是：
```
-----------
|C| | | |A|
-----------
```
计算$A$的值需要上一轮计算的(还未更新的)$A$和$C$的值。
便可以确定推进顺序为 从右到左
$Code$：
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int i,j,T,M,t[101],p[101],f[1001];
int main()
{
scanf("%d%d",&T,&M);
for(i=1;i<=M;i++)
scanf("%d%d",&t[i],&p[i]);
for(i=1;i<=M;i++)
for(j=T;j>=t[i];j--)//从右到左计算
f[j]=max(f[j],f[j-t[i]]+p[i]);//递推
//当需要的左边的值为数组越界时，值不变
printf("%d",f[T]);
return 0;
}
```
------------
现在我们再来看看这题 <疯狂的采药> (终于进入正题)：
其实题目其他地方都没变，只是同一种草药可以反复采摘，而且数据范围增大，如此一来我们无法使用01背包的思路
可以反复采摘同种草药只对我们之前的状态转移方程有一个影响：当 第$i$种草药采了$n$次时，草药种类增加$1$，时间增加$n\times t[i]$，价值增加$n\times p[i]$ ，所以
$$f[i][j]=f[i-1][j-n\times t[i]]+n\times p[i]$$
整理：
$$f[i][j]=max(f[i-1][j],f[i-1][j-n\times t[i]]+n\times p[i])$$
但这样一来时间复杂度就变成了$O(M\times T^T)$，面对$M\le10000,T\le100000$的数据量肯定是要炸的.
```
---------------
|F| |E| |D| |C|
---------------
| | | | |B| |A|
---------------
```
于是将状态转移方程化为上图我们可以注意到： 要求$A$的值需要$C,D,E,F$的值，而求$B$的值需要$D,E,F$的值 ，于是，合并一下，可以得出求$A$的值就需要$B,C$的值，即：
$$f[i][j]=max(f[i-1][j],f[i][j-t[i]]+p[i])$$
又观察可得递推顺序为 从左到右，从上到下
$C++$ 初始代码：
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int i,j,T,M,t[10001],p[10001],f[10001][10000001];
int main()
{
scanf("%d%d",&T,&M);
for(i=1;i<=M;i++)
scanf("%d%d",&t[i],&p[i]);
for(i=1;i<=M;i++)
{
//从左到右
for(j=0;j<t[i];j++)
f[i][j]=f[i-1][j];//针对左边为数组越界的状态
for(j=t[i];j<=T;j++)
f[i][j]=max(f[i-1][j],f[i][j-t[i]]+p[i]);//递推
}
printf("%d",f[M][T]);
return 0;
}
```
其中f[10001][10000001]超过题目所要求的空间上限，所以它也需要压缩
道理一样的：
$$f[j]=max(f[j],f[j-t[i]]+p[i])$$
注意到 $f[j-t[i]]$需要的是这种草药更新后的状态，所以递推顺序应为 从左到右
这和“采药”是不一样的。
另外，题目并没有说明最终结果的范围，需要开longlong以保证数据不溢出
本题 <疯狂的采药> $AC\;C++$ 代码：
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int i,j,T,M;
long long t[10001],p[10001],f[10000001];
int main()
{
scanf("%d%d",&T,&M);
for(i=1;i<=M;i++)
scanf("%lld%lld",&t[i],&p[i]);
for(i=1;i<=M;i++)
for(j=t[i];j<=T;j++)//当需要的左边的值为数组越界时，值不变
f[j]=max(f[j],f[j-t[i]]+p[i]);//递推
printf("%lld",f[T]);
return 0;
}
```
那么，本篇题解到此结束
第一次编辑：$20180126$ 初稿
第二次编辑：$20180816$ 在文章中加入$Markdown$和$Latex$
第三次编辑：$20180818$ 简化部分代码
第四次编辑：$20181002$ 修改少数错误
第五次编辑：$20190227$ 移除$maxf$的修改
第六次编辑：$20190508$ 移除数组初始化
第七次编辑：$20190607$ 还有人觉得看不见递推式？
第八次编辑：$20200727$ 根据反馈，文中对于数组的图例有会影响理解的错误，已更正
第九次编辑：$20200926$ 数据更新