SGU 116 Index of super-prime 数论+完全背包+输出方案

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stack>
#include <set>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 35005;
const int maxm = 10010;
const int INF = 100000;

int prim[maxn];
int s_prim[maxn];
bool vis[maxn];
int tot;
int n;

void work()
{
    memset(vis, 0, sizeof(vis));
    tot = 0;
    prim[tot++] = 2;
    int t = 10010;
    for(int i = 3; i <= t; i += 2)
    {
        if(vis[i])
            continue;

        for(int j = i*i; j <= t; j += 2*i)
            vis[j] = true;

        prim[tot++] = i;
    }
}

int dp[maxm];
int rec[maxm];

int main()
{
    //freopen("in.txt", "r", stdin);

    work();

    int tot2 = 0;
    for(int i = 0; i < tot; i++)
    {
        if(prim[prim[i] - 1] > 10000)
            break;

        s_prim[tot2++] = prim[prim[i] - 1];
    }

    int m;
    scanf("%d", &m);

    fill(dp, dp + 10010, INF);
    dp[0] = 0;

    for(int i = 0; i < tot2; i++)
    {
        for(int j = s_prim[i]; j <= m; j++)
        {
            if(dp[j-s_prim[i]] + 1 < dp[j])
            {
                dp[j] = dp[j-s_prim[i]] + 1;
                rec[j] = j - s_prim[i];
            }
        }
    }

    if(dp[m] == INF)
    {
        printf("0\n");
        return 0;
    }

    int pt = m;
    printf("%d\n", dp[m]);
    while(pt != 0)
    {
        printf("%d", pt - rec[pt]);
        pt = rec[pt];
        printf("%c", " \n"[pt == 0]);
    }

    return 0;
}