不会DFS就这样做

case k=1:.........

2:.........

......................

呵呵~

简单的dfs....

奇怪，我怎么每次拿个鸭蛋？枚举、动规、深搜都用过了，别人的答案也抄过了，就是不AC每次出来的结果都一样，用CANA测试也都过了，难道是数据错位了？

一次ac啊！兴奋。。。庆祝一下。大家别见笑

搜索即是特殊的枚举而已..

深搜不太会。。。这题枚举估计也能AC。。。不过还是练练深搜吧....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

本题动态规划无从下手，也无数学公式可寻，看来只能搜索（组合的生成算法），其实1

数据太弱了

搜索，深搜。

寒死了……我把“readln(n,k)”写成“readln(n); readln(k);”居然过了一个点……………

-_-c.Etta

先求素数集合，然后枚举或DFS都行，组成各种K的组合，相加判断是不是素数，累加，AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DFS……

调试的时候上面写了个cout

DFS，不加剪枝，判断素数用试除，结果是0msAC……

CONST常表，虽然无耻但是很有用

#include <iostream>     //[2002普及组-B]选数
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
int n, k, ans;
ll num[21];
bool isPrime(ll n)
{
    if (n < 2)
        return false;
    int k = sqrt(n);
    for (int i = 2; i <= k; i++)
        if (n % i == 0)
            return false;
    return true;
}

void DFS(int l, ll sum, int t)  //l当前长度, sum当前和, t当前数下标
{
    if(l == k)
    {
        if(isPrime(sum))
            ans++;
    }
    else
        for (int i = t; i < n; i++)
            DFS(l + 1, sum + num[i], i + 1);
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    DFS(0, 0, 0);
    cout << ans << endl;

    return 0;
}

//c++的穷举法，，，
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int p[1230]; //存储10000以内的素数
long x[21];//存储原始数列
int a[21];//存储k个数的选择状态：a[i]=j表示选择的第i个数在原始数列中的下标为j；
long sum;//累加器，统计k个数的和
long total;//统计满足要求的组合个数
int f[10001];//存储1－10000之间数据的状态，f[i]=1表示i为素数，0表示i为非素数
int n,k;
void Get_Prime()//筛选法求1－10000之间的素数
{
memset(p,0,sizeof(p));
int i,j,s;
s=0;
f[1]=0;
for(i=2;i<=10000;i++)
f[i]=1;
for(i=2;i<=10000;i++)
if(f[i]==1)
{
s++;
p[s]=i;
j=2*i;
while(j<=10000)
{
f[j]=0;
j+=i;
}

}

}
bool fit(long sum)
{
int m,Max;
Max=int (sqrt(sum+0.0))+1;//开始没有＋1，测试数据木有通过
m=1;
while(sum%p[m]!=0&&p[m]<Max)
m++;
if(p[m]>=Max)
return 1;
else
return 0;

}

int main()
{

int i,j;
Get_Prime();
while(cin>>n>>k)
{
for(i=1;i<=n;i++)
cin>>x[i];
total=0;
for(i=0;i<=k;i++)
a[i]=i;
while(a[0]==0)
{
sum=0;
for(i=1;i<=k;i++)
sum+=x[a[i]];
if(fit(sum))
total++;
j=k;
while(a[j]==n-k+j)
j--;
a[j]=a[j]+1;
for(i=j+1;i<=k;i++)
a[i]=a[i-1]+1;

}

cout<<total<<endl;

}

return 0;
}

经试验，本题n<=1

#include<bits/stdc++.h>
using namespace std;
int a[25];
int n,k,ans=0;
bool pd(int x)
{
for(int i=2;i*i<=x;++i)
if(x%i==0)return 0;
return 1;
}
void dfs(int now,int w,int t)
{
if(w>n)

}