洛谷 P1832 A+B Problem(再升级)(完全背包)

简介: 算法

题意:

给定一个正整数n,求将其分解成若干个素数之和的方案总数。

思路:

知道是dp,但是想了一会都没去想到完全背包,其实看到拆分就代表素数应该是能无限取的,那么在套用完全背包其实是非常简单的

但是写的时候有点问题,因为状态转移发程和普通的完全背包有点不同。

它的转移方程实际是:dp[i]=dp[i]+dp[i-比他小的素数]

①i是代表从元素i到0有多少种方案

②i较小时DP[0]=1会不断给DP[i]++,所以DP[0]表示有多少种方案可以由i减到0,所以要赋个初值

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+1000;
long long  dp[maxn],v[maxn];
int main()
{
    int n,i,j,t,cnt=0;
    cin>>n;
    for(i=2;i<=1010;i++)
    {
        int f1=0;
        for(j=2;j<=i/2;j++)
        {
            if(i%j==0)
            {
                f1=1;break;
            }
        }
        if(f1==0) v[cnt++]=i;
    }
    dp[0]=1;//当i较小时DP[0]=1会不断给DP[i]++
           //表示有多少种方案可以由i减到0
    for(i=0;i<cnt;i++)
    {
        for(j=v[i];j<=n;j++)
        {
//            dp[j]=max(dp[j],dp[j-v[i]]+1ll); (X) 
//            状态转移方程:dp[i]=dp[i]+dp[i-比他小的素数]
             dp[j]+=dp[j-v[i]];
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}
相关文章
|
5月前
【洛谷 P1219】[USACO1.5]八皇后 Checker Challenge 题解(深度优先搜索+回溯法)
**USACO1.5八皇后挑战**是关于在$n\times n$棋盘上放置棋子的,确保每行、每列及两条主对角线上各有一个且仅有一个棋子。给定$6$作为输入,输出前$3$个解及解的总数。例如,对于$6\times6$棋盘,正确输出应包括解的序列和总数。代码使用DFS解决,通过跟踪对角线占用状态避免冲突。当找到所有解时,显示前三个并计数。样例输入$6$产生输出为解的前三个排列和总数$4$。
38 0
|
6月前
|
算法
[leedcode]刷题有感--动态规划经典问题--01背包问题
[leedcode]刷题有感--动态规划经典问题--01背包问题
|
算法 IDE Java
【洛谷算法题】P1001-A+B Problem【入门1顺序结构】
【洛谷算法题】P1001-A+B Problem【入门1顺序结构】
|
算法 C++
剑指offer(C++)-JZ47:礼物的最大价值(算法-动态规划)
剑指offer(C++)-JZ47:礼物的最大价值(算法-动态规划)
P1865 A % B Problem(欧拉筛,永远的神)
P1865 A % B Problem(欧拉筛,永远的神)
53 0
ACM刷题之路(二十四)HDU 2844 多重背包转换 Coins
ACM刷题之路(二十四)HDU 2844 多重背包转换 Coins
106 0
ACM刷题之路(二十二)多重背包转01背包 HDU 1171
ACM刷题之路(二十二)多重背包转01背包 HDU 1171
|
算法 C++
【PAT甲级 - C++题解】1015 Reversible Primes
【PAT甲级 - C++题解】1015 Reversible Primes
54 0
|
C++
【PAT甲级 - C++题解】1140 Look-and-say Sequence
【PAT甲级 - C++题解】1140 Look-and-say Sequence
74 0
闫氏dp分析法(线性dp)AcWing 1015. 摘花生
闫氏dp分析法(线性dp)AcWing 1015. 摘花生
81 0