NBUT - 1580 调皮的小明（完全背包）

传送门：NBUT - 1580

题目描述

小明是个数学炒鸡棒的小学生， 精通200以内的加法，老师看不下去了，让小明去自学素数，这不，第二天，小明就回到学校，跟全班同学说他有一个问题，把一个数分成一个或多个素数的和，有多少种情况。
9 = 2 + 2 + 2 + 3
9 = 2 + 7
9 = 2 + 2 + 5
9 = 3 + 3 + 3
所以有4种。
老师瞬间呆住了，这小明是吃错药了么。。。不过老师还是希望帮小明解决这个题目。请问你能帮助老师吗？答不出来，老师可是要叫家长咯……

输入描述

多组数据，每组数据输入一个N。2<= N <= 200

输出描述

输出分解的种类数.

思路分析

把题意转化一下，就变成了一个完全背包求方案数的问题，对于N，就是重量为N的背包，物品为小于等于N的所有素数，每个物品可以用无限次，问装满有多少种装法

样例输入

8
9

样例输出

3
4

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;
const int N=1e7+5;

bool ok[N];
int prim[N];
int pos=0;

void p(int n)
{
    memset(ok,true,sizeof(ok));
    ok[0]=ok[1]=false;
    for(int i=2;i<=n;i++)
    {
        if(ok[i])
        {
            prim[pos++]=i;
            for(int j=i*i;j<=n;j+=i)
            {
                ok[j]=false;
            }
        }
    }
}

int dp[222];

int main() {
    p(201);
    int n;
    dp[0]=1;
    for(int i=0;i<46;i++){
            for(int j=prim[i];j<=200;j++){
                dp[j]+=dp[j-prim[i]];
            }
        }
    while(cin>>n){
        cout<<dp[n]<<endl;
    }
    return 0;
}