藍橋杯算法提高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;
}