解题思路:
这题其实很简单,难度不大,只需要用dfs找到任意k个数的和,然后在计算res的时候,枚举判素就可以了,具体的状态转移,大家可以自己画了。。。
代码:
# include<cstdio> # include<iostream> using namespace std; # define MAX 25 int a[MAX]; int res; int n,k; int judge( int x ) { if ( x==0||x==1 ) { return 0; } for ( int i = 2;i*i <= x;i++ ) { if ( x%i==0 ) return 0; } return 1; } void dfs( int st,int flag,int sum ) { if ( flag == k&&judge(sum) ) { res++; return; } if ( st==n ) { return; } for ( int i = st;i < n;i++ ) { dfs(i+1,flag+1,sum+a[i]); } return; } int main(void) { //input 4 3;3 7 12 19 //int n,k; cin>>n>>k; for ( int i = 0;i < n;i++ ) { cin>>a[i]; } dfs(0,0,0); cout<<res<<endl; return 0; }