0分求助

B3624 猫粮规划

张恒灿 @ 2022-05-23 15:50:38

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=45;
int n,l,r,w[maxn],ans;
void dfs(int pos,int sumt){
    if(sumt>=l && sumt<=r) ans++;
    else if(sumt>r) return;
    else{
        int tmp=sumt;
        for(int i=pos;i<=n;i++) tmp+=w[i];
        if(tmp<l) return;
    }
    if(pos==n+1) return;
    dfs(pos+1,sumt);
    dfs(pos+1,sumt+w[pos]);
    return;
}
int main(){
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

为啥是0分?


by Electro_Master @ 2022-05-23 16:52:49

@张恒灿 你这个算重了一些方案,例如有 4 份食物只选 1,2 的方案会在 3,4 被加上两次。


by 张恒灿 @ 2022-05-23 16:55:51

@Electro_Master 在哪里加重了呢?


by 张恒灿 @ 2022-05-23 16:58:19

噢,明白了。谢谢大佬Orz,我自己试着改改。


by Electro_Master @ 2022-05-23 17:00:09

只要你目前的和在 [l,r] 之内就会 ans++ 有可能你这种方案只选了前两个,但是你会在不选 3 和不选 4 之后都 ans++ 这导致算重了。


by 张恒灿 @ 2022-05-23 17:03:17

明白明白,AC了,感谢大佬!


|