洛谷 蓝桥杯砝码称重 第四个测试点

### 蓝桥杯砝码称重问题的C++解法 #### 问题描述 砝码称重问题是经典的动态规划或状态转移问题之一。给定一组不同重量的砝码，目标是计算可以组合出的不同总重量的数量。 以下是基于动态规划的思想实现的一个完整的解决方案： --- #### 动态规划思路解析 该问题可以通过二维布尔数组 `f[i][j]` 来表示前 `i` 个砝码能否组成重量 `j` 的情况。具体来说： - 如果第 `i` 个砝码不参与，则继承上一个状态：`f[i][j] = f[i - 1][j]`; - 如果第 `i` 个砝码放在左侧托盘，则考虑减少其重量的情况：`f[i][j] |= f[i - 1][abs(j - w[i])]`; - 如果第 `i` 个砝码放在右侧托盘，则增加其重量：`f[i][j] |= f[i - 1][j + w[i]]`. 最终统计所有可能的正整数重量即可得出答案[^2]。 --- #### 完整代码实现 以下是一个标准的 C++ 实现方案： ```cpp #include <iostream> #include <vector> using namespace std; const int N = 110, M = 2e5 + 10; bool f[N][M]; int w[N]; int main() { int n; cin >> n; // 输入砝码数量 int m = 0; for (int i = 1; i <= n; ++i) { cin >> w[i]; // 输入每个砝码的重量 m += w[i]; // 计算最大可能重量 } // 初始化 dp 数组 f[0][0] = true; // 填充 dp 表格 for (int i = 1; i <= n; ++i) { for (int j = 0; j <= m; ++j) { f[i][j] = f[i - 1][j]; // 不选当前砝码的状态 if (j >= w[i]) // 放入右侧托盘 f[i][j] |= f[i - 1][j - w[i]]; if (j + w[i] <= m) // 放入左侧托盘 f[i][j] |= f[i - 1][j + w[i]]; } } // 统计可组成的正整数重量数目 int ans = 0; for (int i = 1; i <= m; ++i) { if (f[n][i]) ans++; } cout << ans << endl; // 输出结果 return 0; } ``` 上述代码通过三维压缩的方式实现了动态规划表填充过程，并利用布尔变量记录每种重量的可能性。 --- #### 关键点说明 1. **初始化条件**: 初始状态下只有当没有任何砝码时能够构成零重量，即 `f[0][0] = true`. 2. **状态转移方程**: 对于每一个砝码，分别处理三种可能性（忽略、加入右盘、加入左盘），并更新对应位置的状态。 3. **边界控制**: 防止越界访问，在调整索引时需注意权重范围约束. ---

蓝桥杯是中国最大的IT技能竞赛之一，旨在发现和培养优秀的计算机人才。它由中国教育部主办，每年举办一次。蓝桥杯竞赛分为初赛和决赛两个阶段，初赛是在线考试形式，决赛则是线下实操比赛。 关于砝码称重的Java问题，我需要更多的具体信息才能给出准确的回答。请提供更多细节或者具体的问题，我将尽力帮助你解答。