关于#DFS#的问题，如何解决？(标签-ios|关键词-stream)

Question

洛谷P1036
此题可以用暴力解决，但我希望使用搜索解决。

// Problem: P1036 [NOIP2002 普及组] 选数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1036
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
using namespace std;
int n,k;//n为数列的个数，k为选数的个数
bool zhi(int s)
{
    if(s==0||s==1)    return false;
    else for(int i=2;i*i<=s;i++)
        if(s%i==0)    return false;
    return true;
}
int ans=0;
int arr[30];
int num=0;
int sum=0;
bool brr[30];
void print(bool b[])
{
    for(int i=1;i<=n+3;i++)
        cout<<b[i]<<" ";
}
void dfs(int x)
{
    if(num==k)
    {
        if(zhi(sum))    ans++;
        return;
    }
    for(int i=x;i<=n;i++)
        if(!brr[i])
        {
            num++;
            sum+=arr[i];
            brr[i]=true;
            dfs(x+1);
            num--;
            sum-=arr[i];
            brr[i]=false;
        }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

为何只得了16分？
麻烦各位[旺柴]

Answer 1

不好意思，这段代码中存在一些错误，需要进行修改以确保正确计算。首先，您在搜索质数时的方法有误，应该是对数值进行判断，而不是对索引。其次，在dfs函数中，您没有正确地进行回溯操作来遍历所有可能的选数情况。最后，在主函数中，您应该调用dfs函数来开始搜索，并输出最终的结果。

以下是修改后的代码示例：

#include <
iostream>
using namespace std;
 
bool isPrime(int s) {if (s == 0 || s == 1) return false;
else {for (int i = 2;
 i * i <
= s;
 i++) {if (s % i == 0) return false;
}}return true;
} 
int n, k;
int ans = 0;
int arr[30];
int num = 0;
int sum = 0;
bool brr[30];
 
void print(bool b[]) {for (int i = 1;
 i <
= 30;
 i++){cout <
<
 b[i] <
<
 "
 "
;
}} 
void dfs(int x) {if (num == k) {if (isPrime(sum)) ans++;
return;
}for (int i = x;
 i <
= n;
 i++) {if (!brr[i]) {num++;
sum += arr[i];
brr[i] = true;
dfs(i+1);
num--;
sum -= arr[i];
brr[i] = false;
}}} 
int main() {cin >
>
 n >
>
 k;
for (int i = 1;
 i <
= n;
 i++) {cin >
>
 arr[i];
}dfs(1);
cout <
<
 ans <
<
 endl;
return 0;
}

希望这次能够得到正确的结果。如果您有任何疑问或其他问题，请随时告诉我。

有问题你别着急，评论留言都可以，看到马上就回复，尽量及时补充齐