求助,测试点3
查看原帖
求助,测试点3
218974
wsadjkl0楼主2021/5/9 19:43

照着题解用的记忆化递归,结果第三个测试点出错了呜呜呜,怎么回事啊

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
int f[25][25], a[25];
int is_prime(int x){
	for(int i = 2; i*i <= x; i++)
		if(x%i == 0) return 0;
	return 1;
}
int choose(int k, int sum, int st, int ed){
	if(k == 0) f[k][st] = is_prime(sum);
    if(f[k][st] != -1) return f[k][st];
	
	int pp = 0;
	for(int i = st; i <= ed; i++)
		pp += choose(k-1, sum+a[i], i+1, ed);
		
	return f[k][st] = pp;
}



int main(){
	int n, k;
	cin >> n >> k;
	memset(f, -1, sizeof(f));
	for(int i = 0; i < n; i++) cin >> a[i];
	cout << choose(k, 0, 0, n-1) << endl;;
/*这里是输出的结果
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++)
            printf("%2d ", f[i][j]);
            cout << endl;
    }
 */
	return 0;
}
2021/5/9 19:43
加载中...