悼念512汶川大地震遇难同胞——来生一起走(dfs+打表)
程序员文章站
2022-03-27 13:04:15
题意:5可以有两种 2 3, 5.质数之和因为23 32是重复的由于数据小, 如果数据小于100,连打表都不用#includeusing namespace std;int t, n, m;int dp[100], step, cnt;int judge(int u){ for(int i = 2; i <= sqrt(u); i ++) if(u%i==0)return 0; return 1;}voi.....
- 题意:5可以有两种 2 3, 5.质数之和
- 因为23 32是重复的
- 由于数据小, 如果数据小于100,连打表都不用
#include<bits/stdc++.h>
using namespace std;
int t, n, m;
int dp[100], step, cnt;
int judge(int u){
for(int i = 2; i <= sqrt(u); i ++)
if(u%i==0)return 0;
return 1;
}
void init(){
for(int i = 2; i <= 150; i ++){
if(judge(i))
dp[++step] = i;
}
}
void dfs(int ans, int n, int k){
if(ans > n)return ;
if(ans == n){
cnt ++;
return ;
}
for(int i = k; i <= step; i ++){
dfs(ans+dp[i],n, i);
}
}
int main(){
ios::sync_with_stdio(false);
init();
cin >> t;
while(t --){
cin >> n;
cnt = 0;
dfs(0, n, 1);
cout << cnt << endl;
}
return 0;
}
本文地址:https://blog.csdn.net/xuhang513/article/details/107501642