求条（DFS+剪枝+后缀和）

ouxiyao @ 2024-12-09 19:56:37

#include<iostream>
#include<algorithm>
using namespace std;
int n,l,r,w[64],hzh[64];
long long tot = 0; 
void DFS(int x,int y){
    if(x+1==n){
        tot++;
        return ;
    }
    if(y+hzh[x]<l)return ;
    if(y>r)return ;
    if(x>n)return ;
    DFS(x+1,y+w[x]);
    DFS(x+1,y); 
}
int main(){
    cin>>n>>l>>r;
    for(int i = 1;i<=n;i++)cin>>w[i];
    sort(w+1,w+1+n);
    for(int i = n;i>=1;i--)hzh[i] = hzh[i+1]+w[i];
    DFS(1,0);
    cout<<tot;
    return 0;
} 

by ouxiyao @ 2024-12-09 19:57:29

该不会是后缀和错了吧？

by wujunxi206 @ 2024-12-09 20:03:56

@ouxiyao 原来你在线啊！！！

by ouxiyao @ 2024-12-09 20:29:29

对啊

by ouxiyao @ 2024-12-09 20:30:19

@wujunxi206 帮帮我呗

by wujunxi206 @ 2024-12-09 20:31:44

@ouxiyao

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

int n, l, r, w[64], hzh[64]; // w: 食物能量数组, hzh: 前缀和数组
long long tot = 0; // 总方案数

// 深度优先搜索函数
void DFS(int x, int sum) {
    if (x == n + 1) { // 遍历完所有食物
        if (sum >= l && sum <= r) { // 检查当前方案是否在目标区间内
            tot++;
        }
        return;
    }
    // 选择当前食物
    DFS(x + 1, sum + w[x]);
    // 不选择当前食物
    DFS(x + 1, sum);
}

int main() {
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) { // 注意数组下标从0开始
        cin >> w[i];
    }
    sort(w, w + n); // 对食物能量进行排序（可选，但有助于减少搜索空间）

    // 计算前缀和（这里实际上不需要前缀和数组，因为DFS已经直接计算了组合的和）
    // 但前缀和在某些情况下可以用于优化，这里为了代码完整性保留
    for (int i = 1; i <= n; i++) {
        hzh[i] = hzh[i - 1] + w[i - 1];
    }

    // 从第一个食物开始搜索
    DFS(0, 0); // 注意从0开始，因此DFS的终止条件是x == n + 1

    cout << tot << endl;
    return 0;
}

by ouxiyao @ 2024-12-09 20:32:50

@wujunxi206 《前缀和》杜老师的课你是一个字也没听啊

by ouxiyao @ 2024-12-09 20:37:13

后缀和用来剪枝的

by ouxiyao @ 2024-12-10 17:51:27

@wujunxi206 你这代码6WA4TLE,还来指导我

by wujunxi206 @ 2024-12-10 17:54:06

@ouxiyao 纯AI生成

by ouxiyao @ 2024-12-10 17:57:35

@wujunxi206 AI表示：偶尔(jingchang)撒个谎，别在意