中文题面
你有 \(N\) 根棍子，按顺序使用它们。
- 初始位置在原点右侧附近（代码中用 \(0.5\)）。
- 对于第 \(i\) 根棍子，你可以选择向右延伸（当前位置 \(+a[i]\)），或向左延伸（当前位置 \(-a[i]\)）。
- 如果延伸后位置从正变负，或从负变正（穿过了原点 \(0\)），得分 \(+1\)。
算法
思考：枚举每一步的方向，两种选择。做优化剪枝
#include<bits/stdc++.h>
using namespace std;int n, a[30];
int Ans; void dfs(int k, double pos, int cnt) {// ===================== 剪枝（关键优化） =====================// 如果当前得分 + 剩下所有棍子全穿越 < 已找到的最优解// 剩下棍子数 = n - k + 1// 这种分支不可能更优，直接返回，不再递归if (cnt + (n - k + 1) < Ans) return;if (k == n + 1) {Ans = max(cnt, Ans); return;}double p1, p2;int cnt1, cnt2;// ===================== 选择 1：向右走 =====================p1 = pos + a[k]; if (p1 * pos < 0) cnt1 = cnt + 1; else cnt1 = cnt;dfs(k + 1, p1, cnt1); // 处理下一根棍子// ===================== 选择 2：向左走 =====================p2 = pos - a[k]; // 向左延伸后的位置if (p2 * pos < 0) cnt2 = cnt + 1; else cnt2 = cnt;dfs(k + 1, p2, cnt2); // 处理下一根棍子
}int main(){cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];dfs(1, 0.5, 0);cout << Ans << endl; return 0;
}
核心要点总结
-
穿越判断
新位置 × 原位置 < 0→ 穿过原点 → 得分 +1 -
初始位置 0.5
避免从 0 开始，保证第一次判断有效。 -
剪枝超级重要
cnt + (n - k + 1) < Ans
剩下的棍子就算全部穿越，也超不过当前最优 → 直接剪枝 -
时间复杂度
\(O(2^n)\)，\(n ≤ 20\) 完全能跑过。