11.摆花

[NOIP2012 普及组] 摆花 - 洛谷

---

解题思路：

1.题意为由长度不等的编号由小到大排列，然后从中截取m个数字的长度，如果总和加起来不等，那么视为一个方案数，这应该是很多人看到题目后的模拟策略，类似于在一段序列中，找一段m长度的最长上升子序列问题（数字相邻可以相等），模拟状态太过冗杂，利用深搜又会超时，所以试着用动态规划来解题。

2.使用动态规划，满足最优子结构，如果要求i种花的方案数，往前倒推，那么就是前i-1种方案数然后再加上第i种花的方案数，因为第i种花是有a[i]盆的，意思为可以放的盆数为0-a[i]，当第i种花放的盆数不一样时，前i-1种花放的盆数也不尽相同，所以第i种花的方案数应该是a[i]+1个种方案的累加值。

3.但是题目要求，放m盆即可，意思前i-1种花的数量+第i种花的数量，最大为m盆，那么当第i种花的盆数为k盆时，前i-1种花的盆数应该为m-k盆

4.设置状态：dp[i][j]表示前i种花摆放j盆的方案数

5.状态转移方程为dp[i][j]=dp[i-1][j-k]+dp[i][j];这里的k是第i种花摆放的数量（0<=k<=min(a[i],j）），很明显，k受到了两个条件的制约，既不能超过该类型的数量，也不能超过规定摆放的盆数

6.初始状态： 初始状态设定是最难的（本人看来），不管有多少种花，如果摆放0盆的话，方案数都为1，因为不摆，所以dp[i][0]=1

7.求解目标值：dp[n][m];

---

#include
using namespace std;
int a[110],dp[110][110];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];//记录每种花的数量 
	
	for(int i=0;i<=n;i++)
	dp[i][0]=1; 
	
	for(int i=1;i<=n;i++)//枚举前i种花的编号类型 
	{
		for(int j=1;j<=m;j++)//枚举摆放的盆数 
		{
			for(int k=0;k<=min(a[i],j);k++)//枚举该类型的花能摆放的盆数 
			{
				dp[i][j]=(dp[i][j]+dp[i-1][j-k])%(1000000+7);//累加方案数 
			}
		} 
	}
	cout<//输出目标值 
	return 0;
}