题意
给你两种士兵，n1个A和n2个B，同种士兵是一样的，不分先后，然后你最多能把k1个A排到一起k2个B排到一起，问你有多少种有效排法。
思路
动态规划，建一个三维dp数组，其实是一个二维的表，每个格子有两个值，dp[i][j]表示截至目前只使用i个A，j个B来进行排列，dp[i][j][0]表示以A结尾的排列序列个数,dp[i][j][1]表示以B结尾的排列序列个数，之后我们来转移状态，对于当前的以A结尾的排列，我们可以再其末尾加1～k2个B，构成新的以B结尾的排列，所以我们就可以把dp[i][j+k][1]更新了（k表示加几个B）。同样的，用B结尾排列个数的值更新之后的A结尾排列个数的值，把这个表这样逐步打好，最后输出dp[n1][n2][0]+dp[n1][n2][1]即可。
接下来上代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int dp[120][120][2]; #define MODER 100000000 int main(){ int n1 = 0,n2 = 0,k1 = 0,k2 = 0; memset(dp, 0, sizeof(dp)); cin >> n1 >> n2 >> k1 >> k2; for (int i = 1; i <= k1; i++) { dp[i][0][0] = 1; } for (int j = 1; j <= k2; j++) { dp[0][j][1] = 1; } for (int i = 0; i <= 100; i++) { for (int j = 0; j <= 100; j++) { for (int k = 1; k <= k2; k++) { dp[i][j+k][1] += dp[i][j][0] % MODER; dp[i][j+k][1] %= MODER; } } for (int j = 1; j <= 100; j++) { for (int k = 1; k <= k1; k++) { dp[i+k][j][0] += dp[i][j][1] % MODER; dp[i+k][j][0] %= MODER; } } } cout << (dp[n1][n2][0]+dp[n1][n2][1]+MODER)%MODER << endl; return 0; } |
