jiangfuyu 2011-10-28 23:52:00
点我顶贴
收藏
删除
帮忙看看，为什么只有80分呢
#include <iostream>
#include <cmath>
using namespace std;
int n, k, f = 0, a[20], b[20];
int q(int l, int r) {
int mid = a[(l+r)/2],i=l,j=r;
do{
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j)swap(a[i],a[j]),i++,j--;
}while(i<=j);
}
bool is(int n){
if (n < 2) return false;
for(int i =2; i<=sqrt(n);i++)
if(n%i==0)return false;
return true;
}
int dfs(int d){
if(d>=k){
int sum =0;
for (int i = 0; i < k; i++)sum+=b[i];
if (is(sum)) f++;
}else{
if (d==0) {
for(int i = 0; i < n; i++) {
b[d]=a[i];
dfs(d+1);
}
} else {
for (int i = 0; i < n; i++) {
if (a[i]>b[d-1]){
b[d]=a[i];
dfs(d+1);
}
}
}
}
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
q(0, n - 1);
dfs(0);
cout << f << endl;
system("pause");
return 0;
}