欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

悼念512汶川大地震遇难同胞——来生一起走(dfs+打表)

程序员文章站 2022-07-03 17:49:31
题意: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.....

悼念512汶川大地震遇难同胞——来生一起走(dfs+打表)

  • 题意: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