A27379. 配备书的方案
填空题
较易
知识点
题目描述
配备书的方案
题目描述
中科智慧科技馆里面，科技课程导师要为同学们准备一些科普图书，方便大家阅读。假设一共要选出n本书放在书架上，并且书的种类有m种，包括天文的、计算机的、物理的、化学的、生物的等等。老师会按照每个种类顺序固定的方式摆放好，以方便大家借阅。假设给出每类书现有的数量，请求解出一共有多少种选书方案，也就是总共挑选出n本书（从每种图书中挑选不同的本数），一种有多少种摆放方案？
输入格式
第一行包含两个正整数，分别是m种书，和要摆放在书架上的n本书。
第二行，由空格隔开的每个种类书的数量。
输出格式
输出一行一个整数，表示有多少种图书的摆放方案。
注意：摆放方案数量可能很多，请输出方案数对202307取模的结果。
样例输入
2 4
3 2样例输出
2参考答案
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 202307;
int main() {
int m, n;
cin >> m >> n;
vector<int> books(m);
for (int i = 0; i < m; ++i) {
cin >> books[i];
}
vector<int> dp(n + 1, 0);
dp[0] = 1; // 没有书的时候有一种方案：不选任何书
for (int i = 0; i < m; ++i) {
for (int j = n; j >= 1; --j) { // 从大到小遍历，保证状态不会重叠
for (int k = 1; k <= min(j, books[i]); ++k) {
dp[j] = (dp[j] + dp[j - k]) % MOD;
}
}
}
cout << dp[n] << endl;
return 0;
}
上一题
下一题