洛谷-P5194 [USACO05DEC] Scales S 题解

题目链接：https://www.luogu.com.cn/problem/P5194

题目大意

给定一个天平，最大承重为 C。有 N 个砝码，质量按非降序排列，并且从第 3 个开始，每个砝码的质量 至少等于前两个砝码质量之和（即满足类似斐波那契的性质）。要求选出若干砝码，使得它们的总质量 不超过 C，并且尽可能大。

换句话说：在满足总质量 ≤ C 的前提下，求能选出的最大砝码质量和。

关键观察

1. 砝码序列具有“快速增长”特性

题目中给出一个重要条件：

从第 3 个砝码开始，每个砝码 ≥ 前两个砝码之和。

这意味着砝码序列增长非常快（至少是斐波那契级别），因此：

即使 N = 1000，实际有效的砝码数量也不会太多（因为很快就会超过 C ≤ 2^30）。
更重要的是，这个性质保证了贪心或剪枝搜索的高效性。

2. 暴力枚举不可行，但可以 DFS + 剪枝

直接枚举所有子集（2^N）显然不行（N=1000 太大）。但由于砝码增长快，实际递归深度很小，配合前缀和剪枝，可以高效解决。

解法思路：DFS + 前缀和优化剪枝

我们从最大的砝码开始考虑（倒序处理），对每个砝码有两种选择：

不选它；
选它（前提是加上它不会超过 C）。

为了加速，预处理前缀和 presum[i] = nums[0] + ... + nums[i]。

剪枝策略

在递归函数 process(index, sum) 中（表示当前考虑第 index 个砝码，已选砝码总质量为 sum）：

如果 sum + presum[index] <= C→ 说明从 0 到 index 的所有砝码都可以选，直接取满，更新答案并返回。
否则：先尝试不选当前砝码：process(index - 1, sum)再尝试选当前砝码（如果 sum + nums[index] <= C）：process(index - 1, sum + nums[index])

由于砝码增长快，presum[index] 很快会远大于 C，所以递归树非常浅，效率很高。

正确性证明（关键）

为什么这个 DFS 能找到最优解？

我们遍历了所有可能的合法组合（通过回溯）。
剪枝 if (presum[index] + sum <= c) 是安全的：因为如果剩余所有砝码都能加进去还不超限，那肯定是最优的（加得越多越好），无需再分叉。
由于砝码非负，目标是最大化总和，所以“能全拿就全拿”是正确的贪心选择。

此外，题目中砝码满足“类斐波那契”增长，保证了 presum 增长极快，使得剪枝极其有效，实际运行时间接近 O(N) 或 O(log C)。

代码解析

#include<iostream>
using namespace std;

long long nums[1001], presum[1001];
long long c, n, ans;

void process(int index, long long sum) {
    if (index < 0) {
        ans = max(ans, sum);
        return;
    }
    // 强剪枝：如果剩下的全部加上也不超 C，直接拿完
    if (presum[index] + sum <= c) {
        ans = max(ans, presum[index] + sum);
        return;
    }
    // 不选当前砝码
    process(index - 1, sum);
    // 选当前砝码（如果可以）
    if (sum + nums[index] <= c) {
        process(index - 1, sum + nums[index]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    // 计算前缀和
    presum[0] = nums[0];
    for (int i = 1; i < n; i++) 
        presum[i] = presum[i - 1] + nums[i];
    
    ans = 0;
    process(n - 1, 0); // 从最后一个砝码开始
    cout << ans;
    return 0;
}