帮帮孩子吧，样例过了，结果暴0，给孩子整无语了

bdcml @ 2024-08-06 15:02:24

#include <iostream>
using namespace std;
long long n, l, r, ans;
int w[50];
bool a[50];

void dfs(int step, int sum) {
    if (step > n) {
        if (sum >= l && sum <= r) {
            ans++;
            return ;
        }
    }
    if (sum > r)
        return;

    for (int i = step; i <= n; i++) {
        if (a[i] == 0) {
            a[i] = 1;
            sum += w[i];
            dfs(i + 1, sum);
            a[i] = 0;
            sum -= w[i];
        }
    }
}

int main() {
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}

by lby_commandBlock @ 2024-08-14 20:34:04

@bdcml

if (sum >= l && sum <= r) {
  ans++;
  return ;
}

• 这里 ans++ 后不要 return，有可能再选一个猫粮，能量还是这个范围；
• 不一定非要 step > n 以后才结算，有可能选择中间几个能量也可以，所以第七行代码直接删除；
• 由于 i = step，所有重复情况已经全部排除，所以 a_i 没有任何意义。

改正后代码（已 AC）：

#include <iostream>
using namespace std;
long long n, l, r, ans;
// a[i] 没有任何意义，直接删除
int w[50];

void dfs(int step, int sum) {
    // 不一定非要 step > n
    if (sum >= l && sum <= r) {
        ans++;
    }
    if (sum > r)
        return;

    for (int i = step; i <= n; i++) {
        // 这里删除了 a[i] 的调用
        sum += w[i];
        dfs(i + 1, sum);
        sum -= w[i];
    }
}

int main() {
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}

by bdcml @ 2024-08-15 21:14:08

@lby_commandBlock 谢谢