上海高端网站定制开发,邯郸学做网站学校,网站模板 婴儿,做企业网站要用什么软件题目描述
美羊羊给喜羊羊和沸羊羊出了一道难题#xff0c;说谁能先做出来#xff0c;我就奖励给他我自己做的一样礼物。沸羊羊这下可乐了#xff0c;于是马上答应立刻做出来#xff0c;喜羊羊见状#xff0c;当然也不甘示弱#xff0c;向沸羊羊发起了挑战。 可是这道题目…题目描述
美羊羊给喜羊羊和沸羊羊出了一道难题说谁能先做出来我就奖励给他我自己做的一样礼物。沸羊羊这下可乐了于是马上答应立刻做出来喜羊羊见状当然也不甘示弱向沸羊羊发起了挑战。 可是这道题目有一些难度喜羊羊做了一会儿见沸羊羊也十分头疼于是就来请教你。 题目是这样的 把自然数N100分解为若干个自然数之和求出有几种情况。 如N5时有7种情况 511111 51112 5113 5122 514 523 55 怎么样你要加油帮助喜羊羊哦
输入 一个自然数N(N100 输出 无序拆分的种数。 样例输入 Copy 5 样例输出 Copy 7
题意
给定一个自然数n将其拆分成n1 n2 n3 … nk其中n1 n2 n3 … nk这样称其为一种拆分方案问一共有多少种方案
分析
本题可以等价为 把1,2,3, … n分别看做n个物体的体积这n个物体均无使用次数限制问恰好能装满总体积为n的背包的总方案数即完全背包的变形
朴素做法
思路
f[i][j]表示前 i 个整数1,2…,i恰好拼成 j 的方案数则状态转移方程为
// 选0个i1个i2个i…全部加起来
f[i][j] f[i - 1][j] f[i - 1][j - i] f[i - 1][j - 2 * i] ...;
// 将 j 变为 j - 1 得
f[i][j - i] f[i - 1][j - i] f[i - 1][j - 2 * i] ...;所以可化简为
f[i][j] f[i - 1][j] f[i][j - 1] 初始状态
// 当都不选时方案数是 1即前 i 个物品都不选的情况也是一种方案所以需要初始化为 1
for (int i 0; i n; i ) f[i][0] 1;朴素版代码
#includebits/stdc.husing namespace std;typedef long long LL;const int N 100 10;int n;
LL f[N][N];int main(){ios::sync_with_stdio;cin.tie(0),cout.tie(0);cin n;for (int i 0; i n; i ) f[i][0] 1; // 容量为0时前 i 个物品全不选也是一种方案for (int i 1; i n; i ) {for (int j 0; j n; j ) {f[i][j] f[i - 1][j]; // 特殊 f[0][0] 1if (j i) f[i][j] (f[i - 1][j] f[i][j - i]);}}cout f[n][n] endl;return 0;
}运行时间
所有测试点共9ms
优化做法
思路
for (int i 1; i n; i ) {for (int j 0; j n; j ) {f[i][j] f[i - 1][j]; if (j i) f[i][j] (f[i - 1][j] f[i][j - i]);}
}可以用滚动数组的思想将其转化为一维即
for (int i 1; i n; i ) for (int j i; j n; j ) f[j] (f[j] f[j - i]) % mod;同时将初始状态改为
f[0] 1; // 容量为0时前 i 个物品全不选也是一种方案优化版代码
#includebits/stdc.husing namespace std;typedef long long LL;const int N 100 10;int n;
LL f[N];int main(){ios::sync_with_stdio;cin.tie(0),cout.tie(0);cin n;f[0] 1;for(int i 1;i n;i)for(int j i;j n;j)f[j] f[j] f[j - i];cout f[n];return 0;
}运行时间
所有测试点共9ms
由于本题数据量小n最大只有100故优化后时间变化不明显但数据量很大时会有很明显的优势
