2024-04-24
算法题解
00
请注意,本文编写于 57 天前,最后修改于 54 天前,其中某些信息可能已经过时。

目录

题目分析
第一眼的感觉
再看一眼
分析一下另一条赛道
朴素搜索
剪枝搜索

Last Edit: 2024/1/16 16:32

一个搜索题目,比较神奇

题目分析

第一眼的感觉

欸?一看到下面几个要点:

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

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

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

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

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

这不直接爆内存(125MB)了嘛。

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

再看一眼

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

那么我们就愉快的发现,NN 原来超级小!

分析一下另一条赛道

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

朴素搜索

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

那么我们只需要对于第 xx 个砝码(xNx \le N)考虑两种情况:

  • 使用第 xx 个砝码:加上第 xx 个砝码的重量
  • 不使用第 xx 个砝码:直接跳过 那么可以写出这样的代码:
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 评测记录)。

剪枝搜索

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

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

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

一种方法是,使用前缀和 Sumi=j=1iweightsiSum_i=\sum_{j=1}^{i}{weights_i}。我们可以在处理第 ii 个砝码时,把序号在 [1,i][1, i] 的砝码当作某个特殊的砝码来处理,尝试一次使用多个砝码。如果可以使用,那便没有必要再去尝试分开处理这些砝码了——此时已经得到了局部最优解。 注意,虽然 weightsi[1,230]weights_i\in[1, 2^{30}],但 i=1Nweightsi[1,45230]\sum_{i=1}^{N}{weights_i}\in[1, 45*2^{30}]。而 4523064230=236<263145*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; }

woc,居然能过,有点水评测记录

本文作者:CornWorld

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!