首页 > 代码库 > CSU 1425 Prime Summation

CSU 1425 Prime Summation

2024-07-04 19:17:32   227人阅读

　　原题链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1425

　　DP题。

　　f[i][j]表示当前数字为i，分解式中最大质数为j的方案数，那么，状态转移方程为：

　　　　　　　　　　　　f[i][j] = sum(f[i-j][k])

　　其中，k为小于等于j的所有质数。

　　求具体分解式时可以先转化为从小到大（如样例的“顺数第2”可以表述为“倒数第3”），更容易递推编程。

#include <stdio.h>
#include <string.h>

#define N 205
int n, k;

int f[N][N];

int prime[N], cnt;
bool isprime[N];

void get_prime()
{
    cnt = 0;
    memset(isprime, 0, sizeof isprime);
    for(int i = 2; i < N; i++)
    {
        if(!isprime[i])
        {
            prime[cnt++] = i;
            for(int j = i*2; j < N; j += i)
                isprime[j] = true;
        }
    }
}

int main()
{
    get_prime();
    while(scanf("%d%d", &n, &k) != EOF)
    {
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i = 2; i <= n; i++)
        {
            for(int j = 0; j < cnt; j++)
            {
                if(prime[j] > i) break;
                for(int t = 0; t <= prime[j]; t++)
                    f[i][prime[j]] += f[i-prime[j]][t];
            }
        }
        int sum = 0; 
        for(int i = 0; i <= n; i++)
            sum += f[n][i];
        if(k > sum) k = sum;
        printf("%d\n%d=", sum, n);
        k = sum - k;
        bool flag = false;
        do
        {
            int cnt = 0;
            int i;
            for(i = 2; i <= n; i++)
            {
                if(cnt + f[n][i] > k)
                    break;
                cnt += f[n][i];
            }
            n -= i;
            k = k - cnt;
            if(flag) printf("+");
            flag = true;
            printf("%d", i);
        }
        while(n != 0);
        printf("\n");
    }
    return 0;
}
View Code

 


联系
我们