题解 P1910 【L国的战斗之间谍】

· · 题解

鄙人不才，最近狂写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行的兄台。

以上。