蓝桥杯算法提高VIP-摆花

题目

题目链接

题解

动态规划。

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

dp[i][j]表示i种花，j个盆的方案数，同时也要满足数量的要求。 转移方程： 注意j：0~m；i：1~n。

对于前i种花，我可以选择放0株第i种花，那么剩下的j个盆要放前i-1种花；我也可以选择放1株第i种花，剩下的j-1个盆放前i-1种花；……；我还可以选择放ai株第i种花，剩下的0个盆放前i-1种花。这些方案数累加起来就是前i种花放在j个盆中的方案数。

代码

#include
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 >a[i];
	
	memset(dp, 0, sizeof dp);
	dp[0][0] = 1;
	for(int i = 1;i