题意概括
给定 m m m n n n i i i a i a_i a i m m m n n n n , m ≤ 2000 n, m \le 2000 n , m ≤ 2000 0 ≤ a i ≤ m 0 \le a_i \le m 0 ≤ a i ≤ m n n n m m m n n n a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a 1 , a 2 , … , a n
样例分析
输入：
2 3
2 2
输出：
2
解释：
一共有 2 个盒子和 3 个乒乓球。第 1 个盒子最多放 2 个球，第 2 个盒子最多放 2 个球。
合法的分配方案有以下两种：
第 1 个盒子放 1 个球，第 2 个盒子放 2 个球。
第 1 个盒子放 2 个球，第 2 个盒子放 1 个球。
总计 2 种方案，输出 2。
题目分析
这是一个求非负整数解个数的问题，需要求满足 x 1 + x 2 + ⋯ + x n = m x_1 + x_2 + \dots + x_n = m x 1 + x 2 + ⋯ + x n = m 0 ≤ x i ≤ a i 0 \le x_i \le a_i 0 ≤ x i ≤ a i
可以通过动态规划来求解。定义状态 f i , j f_{i, j} f i , j j j j i i i i i i k k k k k k 0 ≤ k ≤ a i 0 \le k \le a_i 0 ≤ k ≤ a i k ≤ j k \le j k ≤ j
f i , j = ∑ k = 0 min ( j , a i ) f i − 1 , j − k f_{i, j} = \sum_{k=0}^{\min(j, a_i)} f_{i-1, j-k}
f i , j = k = 0 ∑ m i n ( j , a i ) f i − 1 , j − k 按照这个方程直接计算，每次转移需要遍历 k k k n , m ≤ 2000 n, m \le 2000 n , m ≤ 2000 O ( n m 2 ) O(nm^2) O ( n m 2 )
将上述方程展开观察，求 f i , j f_{i, j} f i , j f i − 1 f_{i-1} f i − 1 f i , j − 1 f_{i, j-1} f i , j − 1
$$f_{i, j-1} = \sum_{k=0}^{\min(j-1, a_i)} f_{i-1, j-1-k}
$$将 f i , j f_{i, j} f i , j f i , j − 1 f_{i, j-1} f i , j − 1
$$f_{i, j} - f_{i, j-1} = f_{i-1, j} - f_{i-1, j-a_i-1}
$$移项后即可得到优化后的状态转移方程：
$$f_{i, j} = f_{i, j-1} + f_{i-1, j} - f_{i-1, j-a_i-1}
$$当 j ≤ a i j \le a_i j ≤ a i f i , j = f i , j − 1 + f i − 1 , j f_{i, j} = f_{i, j-1} + f_{i-1, j} f i , j = f i , j − 1 + f i − 1 , j O ( m ) O(m) O ( m ) O ( 1 ) O(1) O ( 1 ) [ 0 , 1000000007 ) [0, 1000000007) [ 0 , 1000000007 )
参考实现
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int a[2005];
ll f[2005][2005];
ll md = 1000000007;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
f[0][0] = 1;
for(int i = 1; i <= n; ++i) {
f[i][0] = f[i-1][0];
for(int j = 1; j <= m; ++j) {
f[i][j] = (f[i][j-1] + f[i-1][j]) % md;
if(j > a[i]) {
f[i][j] = (f[i][j] - f[i-1][j - a[i] - 1] + md) % md;
}
}
}
cout << f[n][m] << "\n";
return 0;
}
复杂度分析
时间复杂度：状态总数为 O ( n m ) O(nm) O ( nm ) O ( 1 ) O(1) O ( 1 ) O ( n m ) O(nm) O ( nm ) O ( n m ) O(nm) O ( nm )
题意概括
给定 m m m n n n i i i a i a_i a i m m m n n n n , m ≤ 2000 n, m \le 2000 n , m ≤ 2000 0 ≤ a i ≤ m 0 \le a_i \le m 0 ≤ a i ≤ m n n n m m m n n n a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a 1 , a 2 , … , a n
样例分析
输入：
2 3
2 2
输出：
2
解释：
一共有 2 个盒子和 3 个乒乓球。第 1 个盒子最多放 2 个球，第 2 个盒子最多放 2 个球。
合法的分配方案有以下两种：
第 1 个盒子放 1 个球，第 2 个盒子放 2 个球。
第 1 个盒子放 2 个球，第 2 个盒子放 1 个球。
总计 2 种方案，输出 2。
题目分析
这是一个求非负整数解个数的问题，需要求满足 x 1 + x 2 + ⋯ + x n = m x_1 + x_2 + \dots + x_n = m x 1 + x 2 + ⋯ + x n = m 0 ≤ x i ≤ a i 0 \le x_i \le a_i 0 ≤ x i ≤ a i
可以通过动态规划来求解。定义状态 f i , j f_{i, j} f i , j j j j i i i i i i k k k k k k 0 ≤ k ≤ a i 0 \le k \le a_i 0 ≤ k ≤ a i k ≤ j k \le j k ≤ j
f i , j = ∑ k = 0 min ( j , a i ) f i − 1 , j − k f_{i, j} = \sum_{k=0}^{\min(j, a_i)} f_{i-1, j-k}
f i , j = k = 0 ∑ m i n ( j , a i ) f i − 1 , j − k 按照这个方程直接计算，每次转移需要遍历 k k k n , m ≤ 2000 n, m \le 2000 n , m ≤ 2000 O ( n m 2 ) O(nm^2) O ( n m 2 )
将上述方程展开观察，求 f i , j f_{i, j} f i , j f i − 1 f_{i-1} f i − 1 f i , j − 1 f_{i, j-1} f i , j − 1
$$f_{i, j-1} = \sum_{k=0}^{\min(j-1, a_i)} f_{i-1, j-1-k}
$$将 f i , j f_{i, j} f i , j f i , j − 1 f_{i, j-1} f i , j − 1
$$f_{i, j} - f_{i, j-1} = f_{i-1, j} - f_{i-1, j-a_i-1}
$$移项后即可得到优化后的状态转移方程：
$$f_{i, j} = f_{i, j-1} + f_{i-1, j} - f_{i-1, j-a_i-1}
$$当 j ≤ a i j \le a_i j ≤ a i f i , j = f i , j − 1 + f i − 1 , j f_{i, j} = f_{i, j-1} + f_{i-1, j} f i , j = f i , j − 1 + f i − 1 , j O ( m ) O(m) O ( m ) O ( 1 ) O(1) O ( 1 ) [ 0 , 1000000007 ) [0, 1000000007) [ 0 , 1000000007 )
参考实现
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int a[2005];
ll f[2005][2005];
ll md = 1000000007;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
f[0][0] = 1;
for(int i = 1; i <= n; ++i) {
f[i][0] = f[i-1][0];
for(int j = 1; j <= m; ++j) {
f[i][j] = (f[i][j-1] + f[i-1][j]) % md;
if(j > a[i]) {
f[i][j] = (f[i][j] - f[i-1][j - a[i] - 1] + md) % md;
}
}
}
cout << f[n][m] << "\n";
return 0;
}
复杂度分析
时间复杂度：状态总数为 O ( n m ) O(nm) O ( nm ) O ( 1 ) O(1) O ( 1 ) O ( n m ) O(nm) O ( nm ) O ( n m ) O(nm) O ( nm )
YIZHIYANG初来乍到 2026-5-19 21:24:49