Luogu P5194 题解

Last Edit: 2024/1/16 16:32

一个搜索题目，比较神奇

题目分析

第一眼的感觉

欸？一看到下面几个要点：

数据范围不大不小，看起来不能搜索（搜索需要 $N<=30$ ），但可以 DP（ $O(N^2)$ 的 DP 需要 $N<=1e4$ ）
存在最优子结构：如果我们任意选择 $x$ 个砝码（ $x<n$ ），我们可以得到子问题的解（可以被认为是局部最优解），多个子问题的解可以合并
决策无后效性："选择某个砝码"这个决策不影响之前已有的决策
存在"有限的容量"（天平最大承重能力 $C$ ），需要满足限制条件（每个砝码只取一次），最大化某些价值（选择的砝码质量和）

那看起来很可以用 01 背包（DP）来做！那来设计一下 DP 方程吧！ DP 状态的设计：令 $F_{i, j}$ 表示用前 $i$ 个物品填满容量为 $j$ 的背包时能达到的最大价值（选择的砝码质量和） DP 转移方程的设计：

存在两种情况，我们进行分类讨论：
- 使用第 $i$ 个砝码：我们需要从容量最合适的位置（即容量为 $j-weights_i$ 处）获取处理第 $i-1$ 个砝码后的状态（子问题解）
- 不使用第 $i$ 个砝码：这样不会对容量产生影响，可以直接从 $i-1$ 处继承处理第 $i-1$ 个砝码时的状态
可以写出 $F_{i, j} = max(F_{i-1, j} , F_{i-1, j-weights_i} + weights_i)$
根据单调性，可以去掉第一维，写出 $F_{j} = max(F_{j} , F_{j-weights_i} + weights_i)$

那就开始写...欸！不对啊，这么说的话， $j<=C$ ，而 $C\in[1, 2^{30}]$ 。如果直接开数组，如：

cpp
const int C=(1<<30);
int f[C];

这不直接爆内存（125MB）了嘛。

那看来 DP 不是一个很好的方案。

再看一眼

继续读题，可以发现一个有意思的条件：这一行中从第 3 个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。 那么我们可以推测出，最特殊的砝码质量序列应该为斐波那契数列（从第三个砝码开始，每个砝码的质量等于前两个砝码质量的和）。而当砝码质量序列为斐波那契数列时，显然这是让每个砝码质量都最小的情况。如果上面可以用 DP，那么这个条件显然是多余的——01 背包不需要序列满足什么性质；显然，这个条件可以改善我们窘迫的情况。回到最初我们分析问题的时候，我们对 $N$ 的大小进行了分析，而我们都知道，斐波那契数列的增长速率是惊人的。当 $N=1e3$ 时， ${Fib}_{1e3}>2^{30}$ （可以使用 Binet 公式 ${Fib}_n=\frac{(1+\sqrt{5})^n}{2^n \sqrt{5}}$ 和对数计算来估计）。那么这个 $N$ 的大小显然是不符合条件的的，所以我们可以估算最大的 $N$ 可以写出下面的代码（不会有人觉得我要用 Binet 公式来算吧？）

cpp
#include <cstdio>
#include <algorithm>

int main() {
	int n=30, cnt=2;
	int x=1, y=1;
	while(y<(1<<n)) {
		int t=x+y;
		x=y;
		y=t;
		++cnt;
	}
	printf("N=%d Fib_N=%d C=%d\n", cnt, y, (1<<n));
	return 0;
}

输出为

plain
N=45 Fib_N=1134903170 C=1073741824

那么我们就愉快的发现， $N$ 原来超级小！

分析一下另一条赛道

那么是不是可以重新考虑一下搜索算法的可行性了呢，毕竟搜索破万法！（搜索算法的适用范围十分广泛）但 $N$ 的范围还是有一些大，我们使用 $O(2^{N})$ （ $N=45$ ）的搜索算法肯定会爆时间，但不妨先写一下看看情况。

朴素搜索

题目条件提到 砝码的质量是一个不下降序列，那么我们可以从根据质量从大到小进行选择。根据 每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和，我们似乎不需要回溯地去考虑曾经做过决策的砝码——这其实是无后效性的表现。

那么我们只需要对于第 $x$ 个砝码（ $x \le N$ ）考虑两种情况：

使用第 $x$ 个砝码：加上第 $x$ 个砝码的重量
不使用第 $x$ 个砝码：直接跳过那么可以写出这样的代码：

cpp
#include <cstdio>
#include <algorithm>

using std::max;

typedef long long ll;

const int N=1e3+11;

int n, c;
int a[N];

ll ans=0;
ll curr=0;
int b[N];

void dfs(int x) {
	if(!x) return;
	
	if(curr+a[x]<=c) {
		// select one
		curr+=a[x];
		ans=max(ans, curr);
		dfs(x-1);
		curr-=a[x];
	}
	
	// select none
	dfs(x-1);
}

int main() {
	scanf("%d%d", &n, &c);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	dfs(n);
	printf("%lld\n", ans);
	return 0;
}

很显然，TLE 了（Luogu 评测记录）。

剪枝搜索

可以考虑一下剪枝能否解决问题。我们可以发现这个题目的解法存在这些性质

当 $C$ 较小时，我们需要用很多小砝码来得到答案
当 $C$ 略小于 $\sum_{i=1}^{n}{weights_i}$ 且不太小时，我们需要几个大砝码和很多小砝码来得到答案
当 $C$ 大于等于 $\sum_{i=1}^{n}{weights_i}$ 时，答案为所有砝码的重量和

注意到，大部分解法需要用到很多小砝码。而在上面的代码，对于所有砝码的处理过程相同。我们是否可以用某些办法批量地使用小砝码呢？

一种方法是，使用前缀和 $Sum_i=\sum_{j=1}^{i}{weights_i}$ 。我们可以在处理第 $i$ 个砝码时，把序号在 $[1, i]$ 的砝码当作某个特殊的砝码来处理，尝试一次使用多个砝码。如果可以使用，那便没有必要再去尝试分开处理这些砝码了——此时已经得到了局部最优解。注意，虽然 $weights_i\in[1, 2^{30}]$ ，但 $\sum_{i=1}^{N}{weights_i}\in[1, 45*2^{30}]$ 。而 $45*2^{30} \le 64*2^{30} = 2^{36} < 2^{63}-1$ （在 long long 类型的范围内），我们有必要给 sum 数组使用 long long 类型。

cpp
#include <cstdio>
#include <algorithm>

using std::max;

typedef long long ll;

const int N=1e3+11;

int n, c;
int a[N];
ll sum[N];

ll ans=0;
ll curr=0;
int b[N];

void dfs(int x) {
	if(!x) return;
	
	// 1. select all
	if(curr+sum[x]<=c) {
		ans=max(ans, curr+sum[x]);
		return;
	}
	
	if(curr+a[x]<=c) {
		// 2. select one
		curr+=a[x];
		ans=max(ans, curr);
		dfs(x-1);
		
		curr-=a[x];
	}
	// 3. select none
	dfs(x-1);
}

int main() {
	scanf("%d%d", &n, &c);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	for(int i=1; i<=n; i++) sum[i]=sum[i-1]+a[i];
	dfs(n);
	printf("%lld\n", ans);
	return 0;
}