1 条题解
-
1
#include <vector> using namespace std; int n, c; vector<int> a; vector<long long> suffixSum; // 后缀和,用于剪枝 vector<int> path; // 记录选中的元素 bool found = false; void dfs(int idx, int currentSum) { if (found) return; if (currentSum == c) { found = true; for (size_t i = 0; i < path.size(); i++) { if (i > 0) cout << " "; cout << path[i]; } cout << endl; return; } if (idx >= n) return; // 剪枝:剩下的所有元素加起来都达不到目标 if (currentSum + suffixSum[idx] < c) return; // 剪枝:当前和已经超过目标 if (currentSum > c) return; // 先尝试包含当前元素(保证"最靠前"的解优先找到) if (currentSum + a[idx] <= c) { path.push_back(a[idx]); dfs(idx + 1, currentSum + a[idx]); path.pop_back(); if (found) return; } // 再尝试不包含当前元素 dfs(idx + 1, currentSum); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> c; a.resize(n); for (int i = 0; i < n; i++) { cin >> a[i]; } // 预处理后缀和 suffixSum.resize(n + 1, 0); for (int i = n - 1; i >= 0; i--) { suffixSum[i] = suffixSum[i + 1] + a[i]; } // 总和都不够,直接无解 if (suffixSum[0] < c) { cout << "No Solution!" << endl; return 0; } dfs(0, 0); if (!found) { cout << "No Solution!" << endl; } return 0; }
- 1
信息
- ID
- 1302
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 8
- 已通过
- 3
- 上传者