【题解】P1855 榨取kkksc03

本文最后更新于 天前,文中部分描述可能已经过时。

某天刷洛谷的时候看到这道题,被标题骗进来了(标题好爽(雾

毋庸置疑这是一道大水题,大概是看在 kkk 的面子上才标了「普及/提高-」难度

那么决定了,第一篇题解就给它吧!(其实只是想练习一下 MathJax 的使用(

题目

P1855 榨取kkksc03

思路

题目的废话很多(其实是洛谷的广告吧),抛开那些废话你会发现这是一道背包问题

我们只需将每个愿望消耗的时间和金钱看作费用,而每个愿望的价值都看作 11,那么这就是一道二维费用的 0101 背包问题

于是乎咱开一个三维数组 f[i][j][k]f[i][j][k],其数值表示前 ii 个愿望恰好消耗 jj 的时间和 kk 的金钱所产生的最大价值,由于我们已经将每个愿望的价值看作 11,产生的最大价值也就等价于最大的愿望数

我们再用 a[i]a[i] 表示第 ii 个愿望所消耗的时间,用 b[i]b[i] 表示第 ii 个愿望所消耗的金钱

根据题意,得出状态转移方程:

f[i][j][k]=max(f[i1][j][k],f[i1][ja[i]][kb[i]]+1)f[i][j][k]=max(f[i-1][j][k],f[i-1][j-a[i]][k-b[i]]+1)

稍微解释一下,对于第 ii 个愿望,有“实现”还是“不实现”两种策略

如果我们实现第 ii 个愿望,那么前 ii 个愿望恰好消耗 jj 的时间和 kk 的金钱所产生的最大价值就等于前 i1i-1 个愿望恰好消耗 ja[i]j-a[i] 的时间和 kb[i]k-b[i] 的金钱所产生的最大价值再加上第 ii 个愿望的价值(也就是 11

如果我们不实现第 ii 个愿望,那么前 ii 个愿望恰好消耗 jj 的时间和 kk 的金钱所产生的最大价值就等于前 i1i-1 个愿望恰好消耗 jj 的时间和 kk 的金钱所产生的最大价值

对于两种策略再取二者中的最大值,就可以得到当前阶段的最优策略

再来看看边界条件,首先初始化三维数组中的每一项为 00,不多解释

其次状态转移方程里有 ja[i]j-a[i]kb[i]k-b[i],有没有想过这两项有可能减出来是负数呢?

所以代码中除了基本的三层循环外,还需要加入判断,一旦两者中存在一者为负,那么我们直接让它继承 f[i1][j][k]f[i-1][j][k] 的数值,也就是:

f[i][j][k]=f[i1][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),对于这道题的数据规模足矣,但是显然还有更加优化的做法

我们可以考虑降维成二维数组进一步优化空间复杂度,事实上 ii 的这一维是可以省去的,只需略微改动一下状态转移方程和循环结构,不断覆盖上一次的无用数据:

f[j][k]=max(f[j][k],f[ja[i]][kb[i]]+1)f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+1)

这样我们就得到了一个空间复杂度为 O(MT)O(M*T) 的做法~

当然还有记忆化搜索等做法,各位可以自己去研究哈~

那么本篇题解就是这样,kkksc03 已经被我们榨取得一滴不剩(大雾)

【题解】P1855 榨取kkksc03
本文作者
Hans362
最后更新
2020-01-25
许可协议
转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!
喜欢这篇文章吗?考虑支持一下作者吧~
爱发电 支付宝

评论

您所在的地区可能无法访问 Disqus 评论系统,请切换网络环境再尝试。