C++: 体检排队问题 - 动态规划解法

解题思路： 本题可以使用动态规划来解决。

假设dp[i][j]表示有i个男同学和j个女同学排队的方案数，其中i>=0，j>=0。

当i=0且j=0时，dp[i][j]=1，表示没有男同学和女同学排队的方案数为1。

当i=1且j=0时，dp[i][j]=1，表示只有一个男同学排队的方案数为1。

当i=0且j=1时，dp[i][j]=1，表示只有一个女同学排队的方案数为1。

当i>=1且j>=1时，dp[i][j]的计算可以分为两种情况：

1. 第一个人是男同学，此时有两种情况：

   • 第二个人是男同学，此时有dp[i-1][j]种排队方案；
   • 第二个人是女同学，此时有dp[i-1][j-1]种排队方案； 所以，如果第一个人是男同学，那么dp[i][j]=dp[i-1][j]+dp[i-1][j-1]。

2. 第一个人是女同学，此时有两种情况：

   • 第二个人是男同学，此时有dp[i][j-1]种排队方案；
   • 第二个人是女同学，此时无法满足条件，所以方案数为0； 所以，如果第一个人是女同学，那么dp[i][j]=dp[i][j-1]。

最终的答案为dp[n][m]。

时间复杂度分析： 动态规划的时间复杂度为O(n*m)。

空间复杂度分析： 动态规划需要使用一个二维数组dp来保存状态，所以空间复杂度为O(n*m)。

完整代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<long long>> dp(n+1, vector<long long>(m+1));
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else if (i == 1 && j == 0) {
                dp[i][j] = 1;
            } else if (i == 0 && j == 1) {
                dp[i][j] = 1;
            } else {
                if (i >= 1) {
                    dp[i][j] += dp[i-1][j];
                    if (j >= 1) {
                        dp[i][j] += dp[i-1][j-1];
                    }
                }
                if (j >= 1) {
                    dp[i][j] += dp[i][j-1];
                }
            }
        }
    }
    
    cout << dp[n][m] << endl;
    
    return 0;
}

时间复杂度分析： 动态规划的时间复杂度为O(n*m)。

空间复杂度分析： 动态规划需要使用一个二维数组dp来保存状态，所以空间复杂度为O(n*m)。