Little_Fox_Fairy @ 2023-07-13 19:16:34
这是代码
#include<bits/stdc++.h>
using namespace std;
int n,l,r,ans;
int w[41],f[41],k[41];
void dfs(int step,int tot,int start)
{
if (tot>=l&&tot<=r)
ans++;
for (int i=start;i<=n;i++)
if (!f[i])
{
tot+=w[i];
f[i]=1;
if (tot>=l&&tot<=r)
ans++;
else
dfs(step+1,tot,i+1);
tot-=w[i];
f[i]=0;
}
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>l>>r;
for (int i=1;i<=n;i++)
cin>>w[i];
dfs(1,0,1);
cout<<ans;
return 0;
}为什么会WA啊······
by weitianjian @ 2023-07-13 19:34:40
if (tot>=l&&tot<=r)
ans++;
else
dfs(step+1,tot,i+1);此处代码逻辑有误。当前答案满足条件，有可能再继续dfs依然可以满足条件。
可以改为如下写法：
void dfs(int step,int tot,int start)
{
if (tot>=l&&tot<=r)
ans++;
for (int i=start;i<=n;i++)
{
tot+=w[i];
if(tot<=r)//可行性剪枝，如果当前答案已经大于r，那么后面一定不会出现新答案
dfs(step+1,tot,i+1);
tot-=w[i];
}
return ;
}by Little_Fox_Fairy @ 2023-07-15 11:25:31
@weitianjian 噢，知道了，谢谢