社区讨论
求各位大佬帮忙看一下哪里错了
P1036[NOIP 2002 普及组] 选数参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @locfaigq
- 此快照首次捕获于
- 2023/10/30 12:51 2 年前
- 此快照最后确认于
- 2023/11/05 00:28 2 年前
基本的思路就是DFS
CPP#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n, k, ans = 0, sum = 0;
int a[N], path[N];
bool st[N];
bool isPrime(int num)
{
if(num < 2) return false;
for(int i = 2; i<=num/ i; i++)
{
if(num % i == 0)
{
return false;
}
}
return true;
}
void dfs(int u) //u代表枚举到了第几个数
{
if(u >= k + 1)
{
//for(int i = 1; i<=k; i++) printf("%d ", path[i]);
//puts("");
for(int i = 1; i<=k; i++) sum += path[i];
if(isPrime(sum)) ans++;
//ans++;
return;
}
for(int i = 1; i<=n; i++)
{
if(!st[i] && path[u - 1] <= a[i])
{
sum += a[i];
st[i] = true;
path[u] = a[i];
dfs(u + 1);
//恢复现场
st[i] = false;
}
}
}
int main()
{
cin>>n>>k;
for(int i = 1; i<=n; i++)
{
cin>>a[i];
}
dfs(1);
cout<<ans<<endl;
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...