【题解】P1855 榨取kkksc03
本文最后更新于 天前，文中部分描述可能已经过时。
某天刷洛谷的时候看到这道题，被标题骗进来了（标题好爽（雾
毋庸置疑这是一道大水题，大概是看在 kkk 的面子上才标了「普及/提高-」难度
那么决定了，第一篇题解就给它吧！（其实只是想练习一下 MathJax 的使用（
题目
思路
题目的废话很多（其实是洛谷的广告吧），抛开那些废话你会发现这是一道背包问题
我们只需将每个愿望消耗的时间和金钱看作费用，而每个愿望的价值都看作 ，那么这就是一道二维费用的 背包问题
于是乎咱开一个三维数组 ，其数值表示前 个愿望恰好消耗 的时间和 的金钱所产生的最大价值，由于我们已经将每个愿望的价值看作 ，产生的最大价值也就等价于最大的愿望数
我们再用 表示第 个愿望所消耗的时间，用 表示第 个愿望所消耗的金钱
根据题意，得出状态转移方程：
稍微解释一下，对于第 个愿望，有“实现”还是“不实现”两种策略
如果我们实现第 个愿望，那么前 个愿望恰好消耗 的时间和 的金钱所产生的最大价值就等于前 个愿望恰好消耗 的时间和 的金钱所产生的最大价值再加上第 个愿望的价值（也就是 ）
如果我们不实现第 个愿望，那么前 个愿望恰好消耗 的时间和 的金钱所产生的最大价值就等于前 个愿望恰好消耗 的时间和 的金钱所产生的最大价值
对于两种策略再取二者中的最大值，就可以得到当前阶段的最优策略
再来看看边界条件，首先初始化三维数组中的每一项为 ，不多解释
其次状态转移方程里有 和 ，有没有想过这两项有可能减出来是负数呢？
所以代码中除了基本的三层循环外，还需要加入判断，一旦两者中存在一者为负，那么我们直接让它继承 的数值，也就是：
（我才不会告诉你我这题 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)，对于这道题的数据规模足矣，但是显然还有更加优化的做法
我们可以考虑降维成二维数组进一步优化空间复杂度，事实上 的这一维是可以省去的，只需略微改动一下状态转移方程和循环结构，不断覆盖上一次的无用数据：
这样我们就得到了一个空间复杂度为 的做法～
当然还有记忆化搜索等做法，各位可以自己去研究哈～
那么本篇题解就是这样，kkksc03 已经被我们榨取得一滴不剩（大雾）
评论