第五十五天 P1036 [NOIP2002 普及组] 选数

#include
#include
#include
#include
using namespace std;
const long long int N=1e8+10;
int a[22],n,k,ans=0;
int sum=0;
bool st[N];

bool prime(int a)
{
    for(int i = 2; i * i <= a; i++)
        if(a % i == 0)
            return false;
    return true;
}

 void dfs(int p,int q)
 {    if (q>k) 
     {
         q--;//计数器回溯
         if(prime(sum))
        {
             ans++;
              
            
        }
    
        return ;
    }
 
    for(int j=p;j<=n;j++)
    {    
        sum=sum+a[j];
        dfs(j+1,q+1);
        
        sum=sum-a[j];//和回溯
        
    
    }
    
     return;
 }

int main()
{    memset(st,0,sizeof(st));
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    //prime();
    dfs(1,1);
    printf("%d",ans);
    
    return 0;
}

费尽心机终于a了。

两个半小时，有一个半小时在debug，烦。

一天一道题真的好慢呀。