题目描述

题目分析

注意不是将 2019 拆分为 2 个质数之和,而是拆分为多个质数之和。
其实是一个 0-1 背包问题,使用动态规划,设 $dp[i][j]$ 为从前 i 个质数中选,和为 j 的方案数,则状态转移方程为
$dp[i][j]=dp[i-1][j],j<prime[i]$
$dp[i][j]=dp[i-1][j]+dp[i-1][j-prime[i]],j>=prime[i]$
既分为不选第 i 个质数和选第 i 个质数两种情况。
初始化 $dp[0][0]=1$。

基础代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
using namespace std;
const int N=2020;

int k=1,flag[N],prime[N];
long long dp[N][N]; //dp[i][j]为从前i个质数中选,和为j的方案数

int main()
{
for(int i=2;i<2019;i++) { //打质数表
if(!flag[i]) {
prime[k++]=i;
for(int j=i+i;j<2019;j+=i) {
flag[j]=1;
}
}
}
dp[0][0]=1;
for(int i=1;i<k;i++) {
for(int j=0;j<=2019;j++) {
dp[i][j]=dp[i-1][j];
if(j>=prime[i]) {
dp[i][j]+=dp[i-1][j-prime[i]];
}
}
}
cout<<dp[k-1][2019]<<endl;

return 0;
}

空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;
const int N=2020;

int k=1,flag[N],prime[N];
long long dp[N];

int main()
{
for(int i=2;i<2019;i++) {
if(!flag[i]) {
prime[k++]=i;
for(int j=i+i;j<2019;j+=i) {
flag[j]=1;
}
}
}
dp[0]=1;
for(int i=1;i<k;i++) {
for(int j=2019;j>=prime[i];j--) {
dp[j]+=dp[j-prime[i]];
}
}
cout<<dp[2019]<<endl;

return 0;
}

题目答案

55965365465060