有些情况根本不用跑

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

三个数组各判一次，数一数 subset_sum 真正被调用了几次，输出如 2/3。（和是奇数的那个，一眼就能否掉，不该占一次调用。）

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 把划分归约到子集和归约做成了没有 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#include <numeric>

bool subset_sum(const vector<int>& arr, int target) {   // 老朋友：能不能挑出子集，和正好是 target
    if (target < 0) return false;
    vector<bool> reach(target + 1, false);
    reach[0] = true;
    for (int x : arr) {
        for (int r = target; r >= x; r--) {
            if (reach[r - x]) reach[r] = true;
        }
    }
    return reach[target];
}

const vector<int> NO = {17, 24, 15, 13, 23};
const vector<int> YES = {10, 20, 15, 5};
const vector<int> ODD = {17, 24, 15, 13, 23, 3};

int calls = 0;

bool subset_sum_counted(const vector<int>& arr, int target) {
    calls++;
    return subset_sum(arr, target);
}

bool can_split(const vector<int>& arr) {
    int s = accumulate(arr.begin(), arr.end(), 0);
    // TODO: 和是奇数就直接返回 false，不要去调 subset_sum_counted；否则才调用它
    (void)s;
    return false;
}

int main() {
    for (const auto& x : {NO, YES, ODD}) can_split(x);
    cout << calls << "/3" << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

有些情况根本不用跑

更多题目

全部评论