在线等,急

B3624 猫粮规划

prg_equal_depressed @ 2023-12-11 22:25:51

#include <iostream>
using namespace std;
int n,l,r,a[50],vis[50],s,x[50];
void dfs(int d){
    if (d>n){
        int cnt=0;
        for (int i=1;i<=d;i++){
            cnt+=x[i];
        }
        if (cnt>=l&&cnt<=r) s++;
        return;
    }
    for (int i=1;i<=2;i++){
        if (!vis[i]){
            if (i==2) x[d]=a[i];
            else x[d]=0;
            vis[i]=1;
            dfs(d+1);
            vis[i]=0;
        }
    }
}
int main(){
    cin>>n>>l>>r;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1);
    cout<<s;
    return 0;
}

五分钟写的,实在没看出来哪有问题,大佬求助,家长催我睡觉了。


by a_big_2B @ 2023-12-13 20:36:23

这不背包么?背包加一个区间不就行了??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????


by ruanwentao666 @ 2023-12-21 21:34:31

同学你好,首先这道题就是一个搜索的问题。 你的代码有以下问题:

  1. 在深搜的循环中,将 id 的含义混淆,胡乱使用
  2. 改完之后发现会超时,需要剪枝:如果当前能量值已经大于 r,则不继续向下搜索。

by prg_equal_depressed @ 2023-12-24 16:09:48

OK,谢谢


by prg_equal_depressed @ 2023-12-24 16:10:49

@a_big_2B 我想用dfs怎么了


|