蓝桥杯算法提高VIP-摆花

题目

题目链接

题解

动态规划。

题目大意：总共n种花，每种花ai株，总共m个盆，花放在盆里的方案数，要求种号小的花必须在种号大的花前面，且同种花不分彼此（不存在内部排序）。

dp[i][j]

表示

i

种花，

j

个盆的方案数，同时也要满足数量的要求。

转移方程：

注意

j

：

0~m

；

i

：

1~n

。

对于前

i

种花，我可以选择放

株第i种花，那么剩下的

j

个盆要放前

i-1

种花；我也可以选择放

1

株第i种花，剩下的

j-1

个盆放前

i-1

种花；……；我还可以选择放

ai

株第i种花，剩下的

个盆放前

i-1

种花。这些方案数累加起来就是前

i

种花放在

j

个盆中的方案数。

代码

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000007, N = 110;

int dp[N][N], a[N], n, m;

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n;i ++) cin>>a[i];
	
	memset(dp, 0, sizeof dp);
	dp[0][0] = 1;
	for(int i = 1;i <= n;i ++)
	for(int j = 0;j <= m;j ++)
	for(int k = 0;k <= a[i] && k<=j;k ++)
	dp[i][j] = ( dp[i][j] + dp[i-1][j-k] ) % MOD; 
	
	cout << dp[n][m] << endl;

	return 0;
}