二维朴素版
#include <iostream>
using namespace std;
const int N = 3000 + 10;
const int M = 1e9 + 9;
int w[20], f[20][N];
void init()
{
w[1] = 1, w[2] = 2;
for(int i = 3; i <= 15; i++) w[i] = w[i - 1] + w[i - 2];
f[0][0] = 1;
for(int i = 1; i <= 15; i++)
{
for(int j = 0; j <= 3000; j++)
{
for(int k = 0; k * w[i] <= j; k++)
{
(f[i][j] += f[i - 1][j - k * w[i]]) %= M;
}
}
}
}
int main()
{
init();
int T; cin>>T;
while(T--)
{
int t; cin>>t;
cout<<f[15][t]<<'\n';
}
return 0;
}
一维优化版
#include <iostream>
using namespace std;
const int N = 3000 + 10;
const int M = 1e9 + 9;
int w[20], f[20][N];
void init()
{
w[1] = 1, w[2] = 2;
for(int i = 3; i <= 15; i++) w[i] = w[i - 1] + w[i - 2];
f[0][0] = 1;
for(int i = 1; i <= 15; i++)
{
for(int j = 0; j <= 3000; j++)
{
for(int k = 0; k * w[i] <= j; k++)
{
(f[i][j] += f[i - 1][j - k * w[i]]) %= M;
}
}
}
}
int main()
{
init();
int T; cin>>T;
while(T--)
{
int t; cin>>t;
cout<<f[15][t]<<'\n';
}
return 0;
}
为什么说这题是一个完全背包的变种呢 你康康下面
//最朴素的三重循环完全背包
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
for(int k = 0; k * w[i] <= j; k++)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
}
}
}
//这题大概思路
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
for(int k = 0; k * w[i] <= j; k++)
{
dp[i][j] += dp[i - 1][j - k * w[i]];
}
}
}
//优化以后
for(int i = 1; i <= n; i++)
{
for(int j = a[i]; j <= m; j++)
{
f[j] += f[j - w[i]];
}
}
注意Mod 1e9
注意不要输一个数跑一遍dp因为时间不允许