START:
2021-08-09
15:28:07
題目鏈接：
https://www.luogu.com.cn/problem/P1832
給定一個正整數n，求將其分解成若干個素數之和的方案總數。
輸入格式
一行：一個正整數n
輸出格式
一行：一個整數表示方案總數
輸入輸出樣例
輸入 #1
7
輸出 #1
3
說明/提示
【樣例解釋】
7=7 7=2+5
7=2+2+3
【福利數據】
【輸入】 20
【輸出】 26
【數據范圍及約定】
對于30%的數據 1<=n<=10
對于100%的數據，1<=n<=10^3
該題 zha 一看是數學題，但是這里可以使用DP。
我們可以將輸入的n視為背包的容量，從1到n的質數的個數看做物品的種類，每個質數看做物品且每個物品可以拿無數次，這就是完全背包問題。 我們定義cnt來計算質數的個數，用sushu[N]數組來儲存每一個質數（下標從0開始），寫一個判斷質數的函數以及初始函數init()，定義dp[N]數組，dp[i]:表示將i分解成質數相加的所有的方案數。那么我們可以知道，對于每一個dp[i]，我們有：dp[i]=dp[i]+dp[i-質數]，并初始化dp[0]=1。這就是核心函數solve()所包含的內容了，下面給出除了solve()函數外所有代碼：
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1005;
int n,cnt=0;
LL sushu[200];
LL dp[N];
bool isprime(int u){
for(int i=2;i<=u/i;i++){
if(u%i==0)return false;
}
return true;
}
void init(){
for(int i=2;i<=n;i++){
if(isprime(i))sushu[cnt++]=i;
}
}
void solve(){
}
int main()
{
cin>>n;
init();
solve();
return 0;
}
現在開始寫solve函數：按照完全背包的模板來：
最外層for循環是遍歷每一個質數，內層循環是遍歷從當前質數sushu[i]到n的所有dp[ ]數組，然后每個dp[i]=dp[i]+dp[i-質數]，所以
dp[j]+=dp[j-sushu[i]];
void solve(){
dp[0]=1;
for(int i=0;i<cnt;i++){
for(int j=sushu[i];j<=n;j++){
dp[j]+=dp[j-sushu[i]];
}
}
cout<<dp[n]<<endl;
}
最后奉上最終代碼：
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1005;
int n,cnt=0;
LL sushu[200];
LL dp[N];
bool isprime(int u){
for(int i=2;i<=u/i;i++){
if(u%i==0)return false;
}
return true;
}
void init(){
for(int i=2;i<=n;i++){
if(isprime(i))sushu[cnt++]=i;
}
}
void solve(){
dp[0]=1;
for(int i=0;i<cnt;i++){
for(int j=sushu[i];j<=n;j++){
dp[j]+=dp[j-sushu[i]];
}
}
cout<<dp[n]<<endl;
}
int main()
{
cin>>n;
init();
solve();
return 0;
}
END:
2021-08-09
15:44:05
浙公網安備 33010602011771號