P1077 [NOIP 2012 普及組] 擺花

題目描述

小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共 $m$ 盆。通過調查顧客的喜好，小明列出了顧客最喜歡的 $n$ 種花，從 $1$ 到 $n$ 標號。為了在門口展出更多種花，規定第 $i$ 種花不能超過 $a_i$ 盆，擺花時同一種花放在一起，且不同種類的花需按標號的從小到大的順序依次擺列。

試編程計算，一共有多少種不同的擺花方案。

輸入格式

第一行包含兩個正整數 $n$ 和 $m$，中間用一個空格隔開。

第二行有 $n$ 個整數，每兩個整數之間用一個空格隔開，依次表示 $a_1,a_2,?,a_n$。

輸出格式

一個整數，表示有多少種方案。注意：因為方案數可能很多，請輸出方案數對 $10^6+7$ 取模的結果。

輸入輸出樣例 #1

輸入 #1

2 4
3 2

輸出 #1

2

說明/提示

【數據范圍】

對于 $20\%$ 數據，有 $0<n\le 8,0<m\le 8,0\le a_i\le 8$。

對于 $50\%$ 數據，有 $0<n\le 20,0<m\le 20,0\le a_i\le 20$。

對于 $100\%$ 數據，有 $0<n\le 100,0<m\le 100,0\le a_i\le 100$。

NOIP 2012 普及組 第三題

solution

動態規劃

• 1 定義公式

•  dp[i][j]: 用前 i 種花擺出 j 盆的方案數量
  

• 2 遞推關系
  • dp[i][j] += dp[i][j - k] // 用k個第i種花
• 3 結果
  • dp[n][m]

實際dp可以省略第一個維度，但是要注意更改順序，防止連鎖反應

代碼

#include <vector>
#include "set"
#include "iostream"
#include "unordered_map"
#include "algorithm"
#include "cstring"
#include "cmath"
#include "iomanip"
#include "cstdio"/** P1077 [NOIP 2012 普及組] 擺花* 題目大意：n種花，每種a[i]盆,擺出m盆,要求同一種花擺在一起,種類按照從小到大的順序選擇，共有多少種擺法* 0<n,m,ai≤100* * 思路：動態規劃* 1 定義公式 *      dp[i][j]: 用前 i 種花擺出 j 盆的方案數量* 2 遞推關系*      dp[i][j] += dp[i][j - k] // 用k個第i種花* 3 結果*      dp[n][m]* 實際dp可以省略第一個維度，但是要注意更改順序，防止連鎖反應*/const int N = 105;
using namespace std;
int n, m, dp[N]; // dp[i][j] 用前 i 種花擺出 j 盆int main() {cin >> n >> m;if (m < n) {cout << 0;return 0;}dp[0] = 1;for (int i = 1, a; i <= n; i++) {cin >> a;for (int j = m; j >= 1; j--) {for (int k = 1; k <= min(a, j); k++) // 第 i 種花可以擺幾種dp[j] += dp[j - k];dp[j] %= 1000007;}}cout << dp[m];return 0;
}

結果