【题解】P1855 榨取kkksc03
本文最后更新于 天前，文中部分描述可能已经过时。
某天刷洛谷的时候看到这道题，被标题骗进来了（标题好爽（雾
毋庸置疑这是一道大水题，大概是看在 kkk 的面子上才标了「普及/提高-」难度
那么决定了，第一篇题解就给它吧！（其实只是想练习一下 MathJax 的使用（
题目
思路
题目的废话很多（其实是洛谷的广告吧），抛开那些废话你会发现这是一道背包问题
我们只需将每个愿望消耗的时间和金钱看作费用，而每个愿望的价值都看作 $1$，那么这就是一道二维费用的 $01$ 背包问题
于是乎咱开一个三维数组 $f[i][j][k]$，其数值表示前 $i$ 个愿望恰好消耗 $j$ 的时间和 $k$ 的金钱所产生的最大价值，由于我们已经将每个愿望的价值看作 $1$，产生的最大价值也就等价于最大的愿望数
我们再用 $a[i]$ 表示第 $i$ 个愿望所消耗的时间，用 $b[i]$ 表示第 $i$ 个愿望所消耗的金钱
根据题意，得出状态转移方程：
$$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-a[i]][k-b[i]]+1)$$
稍微解释一下，对于第 $i$ 个愿望，有“实现”还是“不实现”两种策略
如果我们实现第 $i$ 个愿望，那么前 $i$ 个愿望恰好消耗 $j$ 的时间和 $k$ 的金钱所产生的最大价值就等于前 $i-1$ 个愿望恰好消耗 $j-a[i]$ 的时间和 $k-b[i]$ 的金钱所产生的最大价值再加上第 $i$ 个愿望的价值（也就是 $1$）
如果我们不实现第 $i$ 个愿望，那么前 $i$ 个愿望恰好消耗 $j$ 的时间和 $k$ 的金钱所产生的最大价值就等于前 $i-1$ 个愿望恰好消耗 $j$ 的时间和 $k$ 的金钱所产生的最大价值
对于两种策略再取二者中的最大值，就可以得到当前阶段的最优策略
再来看看边界条件，首先初始化三维数组中的每一项为 $0$，不多解释
其次状态转移方程里有 $j-a[i]$ 和 $k-b[i]$，有没有想过这两项有可能减出来是负数呢？
所以代码中除了基本的三层循环外，还需要加入判断，一旦两者中存在一者为负，那么我们直接让它继承 $f[i-1][j][k]$ 的数值，也就是：
$$f[i][j][k]=f[i-1][j][k]$$
（我才不会告诉你我这题 WA 了两次就是因为这个←_←）
代码
dp 的代码实现还是相对比较容易的，直接上代码：
#include <bits/stdc++.h>
using namespace std;
int f[101][201][201];
int a[101];
int b[101];
int main() {
int n,m,t;
int ans=0;
cin>>n>>m>>t;
for (int i=1; i<=n; i++) {
cin>>a[i]>>b[i];
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
for (int k=1; k<=t; k++) {
if (j>=a[i] && k>=b[i]) {
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-a[i]][k-b[i]]+1);
} else {
f[i][j][k]=f[i-1][j][k];
}
}
}
}
cout<<f[n][m][t]<<endl;
return 0;
}原谅我代码写得这么丑ㄟ(▔ ,▔)ㄏ
反思
这个算法的时间复杂度是 $O(N*M*T)$，空间复杂度也是 $O(N*M*T)$，对于这道题的数据规模足矣，但是显然还有更加优化的做法
我们可以考虑降维成二维数组进一步优化空间复杂度，事实上 $i$ 的这一维是可以省去的，只需略微改动一下状态转移方程和循环结构，不断覆盖上一次的无用数据：
$$f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+1)$$
这样我们就得到了一个空间复杂度为 $O(M*T)$ 的做法～
当然还有记忆化搜索等做法，各位可以自己去研究哈～
那么本篇题解就是这样，kkksc03 已经被我们榨取得一滴不剩（大雾）
评论