斯内克

用户名：Siuving

访问量：16526

签　名：

冰冻三尺非一日之寒

等　　级
排　　名	924
经　　验	3472
参赛次数	0
文章发表	31
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-拦截导弹（O(n*log n)量级）
浏览：609

蓝桥杯算法提高VIP-摆花（C++动态规划分析和优化）
浏览：1487

你可能喜欢

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

蓝桥杯算法提高VIP-摆花（C++动态规划分析和优化）

　　作者: 斯内克　　　　发表时间：2019-11-09 21:19:32 浏览：1487　|　评论：1　

原题链接：蓝桥杯算法提高VIP-摆花

####思路分析：
f[i][j]表示有i种花，能摆j盆花的方案数目

num[i]表示第i种花最多摆放的盆数 
故第i种花可以摆放0,1,2...num[i]盆

此时对前i-1种花，能摆花的盆数可为j-0，j-1，j-2，...，j-num[i]

故此时的方案数，为这些情况方案数的总和

状态转移方程：
f[i][j]=f[i-1][j-0]+f[i-1][j-1]+...+f[i-1][j-num[i]]

即f[i][j]=∑f[i-1][j-k] (k从0到num[i],且j>=k)

赋初值：
i=1时，即只有1种花时，不管j为多少，都只有一种摆法
即f[1][0]=1，f[1][1]=1，...，f[1][num[1]]=1

j=0时，即可摆放花盆的数目为0，此时无论有几种花，都只有1种摆法
即 f[i][0]=1 (1<=i<=n)

####代码1：
```
#include<iostream>
using namespace std;
const int N=110;
int num[N],f[N][N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>num[i];
	//赋初值
	for(int i=1;i<=n;i++) f[i][0]=1;
	for(int j=0;j<=num[1];j++) f[1][j]=1;
	
	//状态的更新
	for(int i=2;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<=num[i]&&k<=j;k++)
				f[i][j]=(f[i][j]+f[i-1][j-k])%1000007; 
	cout<<f[n][m]<<endl;//输出最多类别情况的方案数，即最多的方案数
	return 0;
}
```
####优化分析：
有上述分析不难发现，f[i][j]在运算中，仅和f[i-1][]有关。

故设想能不能用一维数组来存储值？ 
若用f[j]来表示f[i][j]，故运算和f[j-k]有关。
	
那么**重点**来了:

如果和上述一样，j从1开始枚举到m，会造成此时的f[j-k]并不是上一轮的值，而是新一轮已经更新过的值。

我们要求的是加上一轮的值，即f[i-1][]的值。

如果我们让j从m开始枚举到1，由于状态更新是从后往前，更新的值并不会影响后续的更新，所以是可行的。
####代码2：
```
#include<iostream>
using namespace std;
const int N=110;
int num[N],f[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>num[i];
	//赋初值
	f[0]=1;
	
	//状态的更新
	for(int i=1;i<=n;i++)
		for(int j=m;j>=1;j--)
			for(int k=1;k<=num[i]&&k<=j;k++)
//这里k要从1开始枚举，因为上面的f[i][j]初值为0。
//而这里f[j]有初值，为上一轮的值，可理解为f[i-1][j]的值，若k从0开始枚举，会加两次,造成方案重复。
				f[j]=(f[j]+f[j-k])%1000007; 
	cout<<f[m]<<endl;
	return 0;
}
```

0.0分

25 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

jhrsya

写的很好，谢谢

2020-03-23 10:49:00

斯内克

TA的其他文章

你可能喜欢

C二级辅导-等差数列（C语言代码）

C二级辅导-阶乘数列（C语言代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

蓝桥杯算法提高VIP-摆花（C++动态规划分析和优化）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

蛇行矩阵（C语言代码）

时间转换（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

生日日数（C语言代码）

斯内克

TA的其他文章

你可能喜欢

C二级辅导-等差数列 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C语言训练-舍罕王的失算 （C++代码）（都给答案了还算什么）

蓝桥杯算法提高VIP-摆花 （C++动态规划分析和优化）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

蛇行矩阵 （C语言代码）

时间转换 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

生日日数 （C语言代码）

C二级辅导-等差数列（C语言代码）

C二级辅导-阶乘数列（C语言代码）

用筛法求之N内的素数。（C++代码）

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

蓝桥杯算法提高VIP-摆花（C++动态规划分析和优化）

　　评论区

蛇行矩阵（C语言代码）

时间转换（C语言代码）

生日日数（C语言代码）