solution
此题有两种解法。
第一种解法就是裸的完全背包。
就相当于有n种物品,第i种物品的重量是i。每种物品有无限多个,问恰好填满一个容量为n的背包的方案数。
第二种解法是生成函数。
用生成函数表示拆分出的的数量。用表示拆分出的的数量。剩下的同理。最终的系数就是答案。
code
解法1
/* * @Author: wxyww * @Date: 2020-04-16 14:18:39 * @Last Modified time: 2020-04-16 14:19:55 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int f[150]; int main() { int n; while(~scanf("%d",&n)) { memset(f,0,sizeof(f)); f[0] = 1; for(int i = 1;i <= n;++i) { for(int j = i;j <= n;++j) f[j] += f[j - i]; } cout<<f[n]<<endl; } return 0; }
解法2
/* * @Author: wxyww * @Date: 2020-04-16 14:11:40 * @Last Modified time: 2020-04-16 14:19:27 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 150; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int f[N][N],tmp[N]; int main() { int n; while(~scanf("%d",&n)) { memset(f,0,sizeof(f)); for(int i = 0;i <= n;++i) f[1][i] = 1; for(int t = 2;t <= n;++t) { for(int i = 0;i <= n;++i) { for(int k = 0;k + i <= n;k += t) { f[t][i + k] += f[t - 1][i]; } } } cout<<f[n][n]<<endl; } return 0; }