地址 https://www.papamelon.com/problem/225
有 n 种物品，第i 种物品有 a_i个。
不同种类的物品可以互相区分但相同种类的无法区分。从这些物品中取出 m 个物品的话，有多少种取法？
求出方案数模 M 的余数。
输入
输入第一行有三个整数n、m、M, 第二行有n个整数,表示数组a_i
1≤n≤1000
1≤m≤1000
1≤ai≤1000
2≤M≤10000
输出
输出一个整数,表示方案数模 M 的余数
样例 1
输入
3 3 10000
1 2 3
输出
6
解法
动态规划优化
dp[i][j] 表示前i组取出j个的方案数目
还要根据j和ai的数目分开讨论
j <= ai
(1) dp[i][j] = dp[i-1][j] + dp[i-1][j-1]~~~~dp[i-1][0]
j > ai
(2) dp[i][j] = dp[i-1][j] + dp[i-1][j-1]~~~~dp[i-1][j-ai]
同样的 dp[i][j-1] 也能得到两个状态转移 并且可以和上面的式子进行优化
j <= ai
(3) dp[i][j-1] = dp[i-1][j-1]+dp[i-1][j-2]~~~~dp[i-1][0]
j > ai
(4) dp[i][j-1] = dp[i-1][j-1] + dp[i-1][j-2]~~~~dp[i-1][j-ai]+dp[i-1][j-1-ai]
(1)和(3)可以优化
dp[i][j] - dp[i][j-1] = dp[i-1][j];
(2)和(4)可以优化
dp[i][j] - dp[i][j-1] = dp[i-1][j] - dp[i-1][j-1-ai];
综合所得 状态转移公式
j <= ai
dp[i][j] = dp[i-1][j] + dp[i][j-1]
j > ai
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1-ai]
得到状态转移公式就得到了流程
代码如下
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, M;
int a[N];
int dp[N][N];
int main()
{
cin >> n >> m >> M;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i <= n; i++) { dp[i][0] = 1; }
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= 1 && j <= a[i]) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
else {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1 - a[i]];
}
dp[i][j] = (dp[i][j]+M) % M;
}
}
cout << dp[n][m] << endl;
return 0;
}