描述
m 个相同的乒乓球分到 n 个不同的盒子中,已知第 i 个盒子最多能容纳 ai
个乒乓球。所有乒乓球要求必须分完,求分配方案数。
答案对 1000000007 取模。
输入描述
输入共2行。
第1行2个整数,n,m,表示盒子的数量和乒乓球数量。
第2行 n个数用空格隔开,表示每个盒子最多可容纳乒乓球的数量。
输出描述
输出1行1个整数,表示分配方案数,答案对1000000007取模。
用例输入 1
3 5
2 2 3
用例输出 1
6
用例输入 2
2 21
10 10
用例输出 2
0
用例输入 3
3 100000
100000 100000 100000
用例输出 3
149966
c++帮帮我吧总TLE
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
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 - 1] && k <= j; ++k) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
}
}
}
cout << dp[n][m] << endl;
return 0;
}
7个对 四个TLE