Sum of Different Primes——素数表+dp

素颜马尾好姑娘i 2022-06-14 04:40 144阅读 0赞

Think:  
1题意：输入n(n <= 1120), k(k <= 14)，询问由k个不同素数相加得到n的方案数，\{2， 4\}，\{4， 2\}属于一种方案，输入0, 0表示结束，不作处理  
2思路：素数表+dp  
3反思：  
1>dp状态转移方程不理解，需要进行专题练习或知识复习  
2>注意状态转移方程中重复元素情况的处理

[vjudge题目链接][vjudge]  
[建议参考博客][Link 1]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int v[1400], dp[1400][24];
    
    void Init();
    
    int main(){
        Init();
        int n, k;
        while(scanf("%d %d", &n, &k) && (n || k)){
            printf("%d\n", dp[n][k]);
        }
        return 0;
    }
    void Init(){
        memset(v, 0, sizeof(v));
        memset(dp, 0, sizeof(dp));
        int i, j, k;
        v[1] = 1, v[2] = 0;
        for(i = 2; i <= 1400; i++){
            if(!v[i]){
                for(j = i*2; j <= 1400; j += i){
                    v[j] = 1;
                }
            }
        }
    
        dp[0][0] = 1;
        for(i = 2; i <= 1120; i++){
            if(!v[i]){
                for(j = 14; j >= 1; j--){
                    for(k = 1120; k >= i; k--){
                        dp[k][j] += dp[k-i][j-1];
                    }
                }
            }
        }
    }

[vjudge]: https://vjudge.net/problem/UVA-1213
[Link 1]: http://blog.csdn.net/squee_spoon/article/details/38293055

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关 Sum of Consecutive Prime Numbers

4.Sum of Consecutive Prime Numbers Some positive integers can be represented by a

怼烎@/ 2023年07月08日 02:52/ 0 赞/ 6 阅读

相关 Difference Between Primes（素数打表，素数表与数表通用）

Difference Between Primes Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 327

喜欢ヅ旅行/ 2022年08月01日 13:53/ 0 赞/ 170 阅读

相关 POJ2739 Sum of Consecutive Prime Numbers

题目大意：给出一个数n，判断n是否可以被连续质数的和表示，可以的话，输出可能的情况总数。输入以0结束。 include <iostream> usi

心已赠人/ 2022年07月11日 12:08/ 0 赞/ 155 阅读

相关 POJ 2739 Sum of Consecutive Prime Numbers

> Sum of Consecutive Prime Numbers > Time Limit: 1000MS Memory Limit: 65536K > Total

川长思鸟来/ 2022年06月16日 09:16/ 0 赞/ 119 阅读

相关 Sum of Consecutive Prime Numbers UVA - 1210——素数表+初级dp思想

Think: 1题意：输入正整数n(2 <= n <= 10000),求连续素数之和等于n的方案数 2思路： 1>筛法建立素数表+初级dp思想(从后往前规划得到当前

逃离我推掉我的手/ 2022年06月14日 04:49/ 0 赞/ 157 阅读

相关 Sum of Different Primes——素数表+dp

Think: 1题意：输入n(n <= 1120), k(k <= 14)，询问由k个不同素数相加得到n的方案数，\{2， 4\}，\{4， 2\}属于一种方案，输入0,

素颜马尾好姑娘i/ 2022年06月14日 04:40/ 0 赞/ 145 阅读

相关 Prime Gap UVA - 1644——筛法建素数表

Think: 1题意：输入一个整数n，输出后一个素数和前一个素数的差值，输入是素数时输出0，n不超过1299709（第100000个素数），输入0时结束不进行操作 2方

￡神魔★判官ぃ/ 2022年06月14日 04:39/ 0 赞/ 156 阅读

相关 UVA - 10789 - Prime Frequency（素数打表）

题意是给出0-9，A-Z，a-z，组成的字符串，如果字符的个数是素数就输出这个字符。例如ABCC中的C的个数是素数，那么输出C；首先素数打表，剩下的就是如何储存每个

浅浅的花香味﹌/ 2022年06月07日 00:21/ 0 赞/ 189 阅读

相关素数 + 背包 - SGU 116. Index of super-prime

> Index of super-prime [ Problem's Link][_Problem_s Link] ------------------

╰半夏微凉°/ 2022年03月30日 04:14/ 0 赞/ 134 阅读

相关 Sum of Consecutive Prime Numbers

一些正整数能够表示为一个或多个连续素数的和。给定一个正整数，有多少个这样的表示？例如，整数53有两个表示5+7+11+13+17和53；整数20没有这样的表示。注意加法操

约定不等于承诺〃/ 2022年03月29日 12:58/ 0 赞/ 166 阅读