首页 > 分享 > 【动态规划】摆花

【动态规划】摆花

花匠小妙招
2024-11-06 20:24

一:题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入输出格式

输入格式：
第一行包含两个正整数n和m，中间用一个空格隔开。

第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、……an。

输出格式：
输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对1000007取模的结果。

输入输出样例
输入样例#1：
2 4
3 2
输出样例#1：
2

说明
【数据范围】

对于20%数据，有0<n≤8，0<m≤8，0≤ai≤8；

对于50%数据，有0<n≤20，0<m≤20，0≤ai≤20；

对于100%数据，有0<n≤100，0<m≤100，0≤ai≤100。

NOIP 2012 普及组第三题

二:解题思路—— 搜索

这道题我刚看到的时候，想到的是dfs的解法，每一次对每一盆花，我们都有0～a[i]种选法，然后又因为花的摆放需要按照顺序摆放，因此，只需每一次往下一层递归，每次选花的时候枚举所有的选法，那么就能完成目标。但是因为数据量较大，因此代码会超时。

#include<bits/stdc++.h> using namespace std; int a[1000],f[1000]; int n,m,res; void dfs(int dep,int sum)//dep为当前在选第几盆花，sum表示当前选了多少盆 {if(sum>m)return;if(sum==m){res++;return;}for(dep>n)return;for(int i=0;i<=a[dep];i++)dfs(dep+1,sum+i); } int main(){cin >> n >> m;for(int i=1;i<=n;i++)cin >> a[i];dfs(1,0);cout << res;return 0; }

123456789101112131415161718192021222324252627

三:解题思路—— 记忆化

对于搜索来说最为经典的一种优化方式就是记忆化了，我们把已经访问过的情况都做记录，下次再访问到同样的情况时，只需要查看记录就可以了，具体在这一题中如何记录呢？
下面，我给出一个测试数据：

4 5
1 2 2 2

假设我当前的我当前的情况下，我已经选了一盆序号为1的花，和一盆序号为2的花：

1 2 空空空

那么，我在这种情况下，剩下来的情况一共有

1 2 3 3
1 2 3 4
1 2 4 4

也就是说，进入下一层递归的时候，我们的dep=3，sum=2
在另外一种局面的情况一下，我当前选了两盆序号为2的花

2 2 空空空

在这种情况下，剩下来的情况一共有

2 2 3 3
2 2 3 4
2 2 4 4

同时，我们进入下一层递归的时候参数依然是dep=3，sum=2
那么也就是说，不管前面两个是什么数字，当我出现dep=3，sum=2的情况时，后面必定只有3种情况

? ? 3 3
? ? 3 4
? ? 4 4

因此，我们可以把这种状态记录下来，而这种记录下来的过程就称之为记忆化，当我们调用下一层递归的时候，我们判断一下是否当前的状态已经被访问过了，如果访问过了就直接返回我们的结果，同时，我们的递归函数需要修改一下，增加一个返回值，参考代码如下：

#include <iostream> using namespace std; int a[1000],f[110][110]; int n,m; int dfs(int dep,int s) { int res = 0; if(s == m) return 1; if(dep > n || s > m) return 0; if(f[dep][s]!=0) return f[dep][s]; for(int i=0;i<=a[dep];i++) res = (res+dfs(dep+1,s+i))%1000007; f[dep][s] = res; return res; } int main() { cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; cout << dfs(1,0) % 1000007; return 0; }

1234567891011121314151617181920212223242526

四:解题思路—— 动态规划

所有可以使用记忆化搜索的程序，都可以修改成动态规划来求解。
我们定义一个f[i][j] ，表示当前只有前i个物品，且只摆放j盆花的情况下，总共有多少种摆法。
f[0][0]=1; 表示当没有物品的时候，总共有一种情况，就是没有物品，
我们拿这组数据举例

4 5
1 2 2 2

每一次看i号花盆的时候，假设当前要摆放的花的数量是j，那么我们就去求出i-1号花盆数量为j-1,j-2,…j-a[i]的时候的和，那么就是
在这里插入图片描述

通过以上的数据，我们经过一系列递推，可得到以下表格（表格为手写，字比较丑）

在这里插入图片描述
最后得到我们的代码：

#include <iostream> #include <string.h> using namespace std; int a[1000],f[110][110]; int n,m; int main() { cin >> n >> m; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) cin >> a[i]; f[0][0]=1; for(int i=1;i<=n;i++) for(int k=0;k<=a[i];k++) for(int j=m;j>=k;j--) f[i][j]=(f[i][j]+f[i-1][j-k])%1000007; cout << f[n][m] << endl; return 0; }

12345678910111213141516171819