自动搬运

查看原文

来自洛谷，原作者为

	MuelsyseU 行き場のない声の淵か 赤い水が流れ落ちるのら

搬运于2025-08-24 21:31:48，当前版本为作者最后更新于2019-11-08 22:00:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

鄙人不才，最近狂写DP空间压缩的题解，不知道在想什么

1. 前言

二维动态规划题。

数据虽水，然该压还是得压 （说实话除了需要压缩空间之外就是大水题）。本文主要讲空间的压缩，针对对背包已有基础的童鞋，如不了解基本思路请参照其它$dalao$的题解。

关于二维动规本人可能讲不太细，众$dalao$见谅。

2. 关于题目思想

题目P1910主要内容为：有$N$个间谍，最多伪装能力总和不能高 (低？) 于$M$，拥有的费用为$X$元。给出每个间谍可获取的情报量、伪装能力值、所需的费用，求最多可获得多少情报。

3. 关于算法思想

可以看到，贪心是不可取的。虽然我不能具体说出为什么不可取

于是我们想到两条路子：搜索和动规。

搜索是一个并不好的算法，但是根据范围问题可以发现并不太可取 （当然可以尝试记忆化大法）。

尽管数据的奇异使搜索可能AC，但实际上不是所有数据都这么幸运。

---

我们考虑二维动规。

首先从一维角度来看（不考虑费用），这是$01$背包。

于是设$f[i][j]$表示前$i$人中伪装能力至多为$k$的最大获取资料量$(1<=i<=N,0<=j<=M)$，其中$v[i]$表示第$i$人可获取得资料量，$w[i]$表示派出第$i$人的伪装能力（越大越差）。

于是对于 $0<=w[i]<=j$，有$f[i][j]=Max(f[i-1][j],f[i-1][j-w[i]]+v[i])$。

---

现在加入$p[i]$表示第$i$人所需的费用，则同理有$f[i][j][k]$表示前$i$人中伪装能力至多为$k$且总费用为$j$的最大获取资料量 （很乱有木有）。$(1<=i<=N,0<=j<=M,0<=k<=X)$

则对于 $0<=w[i]<=j,0<=p[i]<=k$，有$f[i][j][k]=Max(f[i-1][j][k],f[i-1][j-w[i]][k-p[i]]+v[i])$。

上式根据$01$背包基本思路比较好证明，即对于不取第$i$人，由前$i-1$人的状态推出；对于取第$i$人，由“前$i-1$人剩余$j-w[i]$的伪装能力和$k-p[i]$的费用可用”时的状态加上可获取资料量推出。

---

整理思路，首先二重循环输入数据存储于$a[]$、$b[]$和$c[]$中，再设一$f[][][]$用三重循环求解后，输出$f[N][M][X]$。

参考代码如下：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int a[105],b[105],c[105];
int f[105][1005][1005];
int main(){
	int n,m,p;
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i]>>c[i];
	for(int i=1;i<=n;i++)
		for(int j=m;j>=b[i];j--)
			for(int k=p;k>=c[i];k--)
				f[i][j][k]=max(f[i-1][j][k],f[i-1][j-b[i]][k-c[i]]+a[i]);
	cout<<f[n][m][p];
	return 0;
} 

然而似乎非常不幸：

众看官是否发现了代码中的$f[105][1005][1005]$？1e8的巨大数组成功MLE此题。

于是自然可以想到压缩的问题：

3. $a,b,c$压缩

这部分是本人的拿手压缩虽然常常无用，即输入部分的压缩。

首先让我们抛开$f$数组，考虑$a,b,c$三个数组。

注意以下代码段：

for(int i=1;i<=n;i++)
	cin>>a[i]>>b[i]>>c[i];
for(int i=1;i<=n;i++)
	for(int j=m;j>=b[i];j--)
		for(int k=p;k>=c[i];k--)
			f[i][j][k]=max(f[i-1][j][k],f[i-1][j-b[i]][k-c[i]]+a[i]);

可以发现第二个循环部分每次都仅使用了$a[i],b[i],c[i]$三个值，因此我们可以将两个循环合二为一，同时将这三个数组直接压缩成$x,y,z$三个临时变量。

参考代码如下：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int x,y,z;
int f[105][1005][1005];
int main(){
	int n,m,p;
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>z;
		for(int j=m;j>=y;j--)
			for(int k=p;k>=z;k--)
				f[i][j][k]=max(f[i-1][j][k],f[i-1][j-y][k-z]+x);
	}
	cout<<f[n][m][p];
	return 0;
}

4. $f$数组压缩

动规的经典压缩方式（f压缩到二维）。

由上述内容可以看出，在计算第$i$人时，仅需使用 $f[i-1][][]$ 的数据，其前的值可以舍弃——最终可直接舍弃 $f[n][][]$ 之前的所有值。

这样看来，不妨直接使用方程$f[j][k]=Max(f[j][k],f[j-w[i]][k-p[i]]+v[i])$。

仔细观察方程，可发现每次 i 循环都更新了$f[][]$中的值，这样，在执行完第 i-1 层循环后，f 数组就保存了第 i-1 层的所有数据。

其后第 i 层循环，实际上等同于使用$Max(f[i-1][j][k],f[i-1][j-w[i]][k-p[i]]+v[i])$来更新$f[i][j][k]$。

最后要注意一点，大部分这类压缩都要注意循环方向的问题，如此题状态转移需用到的数据为$f[j][k],f[j-w[i]][k-p[i]]$，即所使用的下标不超过$j$和$k$，需采取由$n$到$j,k$的循环方向，否则将错误地使用到$f[i][j-w[i]][k-p[i]]$。

当然本题本身是$01$背包，因此循环方向本身就满足要求，只是要记住这一点。

整理思路，即是：将$f$数组变为一维，所有类似$f[i][j][k]$形式的部分改为$f[j][k]$形式。

参考代码如下：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int x,y,z;
int f[1005][1005];
int main(){
	int n,m,p;
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>z;
		for(int j=m;j>=y;j--)
			for(int k=p;k>=z;k--)
				f[j][k]=max(f[j][k],f[j-y][k-z]+x);
	}
	cout<<f[m][p];
	return 0;
} 

5. 总结

越研究$Luogu$的题解要求越觉得自己的题解过不了……不过感觉这篇应该还蛮详细的吧……（大嘘）

感觉自己花式把一个简单的正解写得复杂之极……当然其中压缩的部分说不定还有些用处，毕竟$Luogu$详细写如何压缩$f$的题解似乎并不多。

最后，感谢阅读完这175行的兄台。

以上。