C++实现小X喜欢下棋。 这天小X对着一个长为N宽为M 的矩形棋盘发呆突然想到棋盘上不仅可以放棋子 还可以放多米诺骨牌。 每个骨牌都是一个长为2宽为1的矩形当然可以任意旋转。小X想知道在骨牌两两不重叠的前提下这个棋盘上最多能放多少个骨牌希望你帮帮他

这个问题可以通过动态规划来解决。

我们可以定义一个二维数组dp，其中dp[i][j]表示在前i行、前j列的棋盘上最多能放多少个骨牌。初始状态下，所有的dp[i][j]均为0。

然后，我们可以通过状态转移方程来更新dp数组。对于dp[i][j]而言，有以下几种情况：

1. 如果当前位置(i, j)已经放了一个骨牌，那么dp[i][j] = dp[i][j-1]，即当前位置的放置情况与前一列的放置情况相同。
2. 如果当前位置(i, j-1)和(i, j)都没有放骨牌，那么dp[i][j] = dp[i][j-2] + 1，即当前位置的放置情况是在前两列的放置情况基础上加1。
3. 如果当前位置(i, j)已经放了一个骨牌，那么dp[i][j] = dp[i-1][j]，即当前位置的放置情况与前一行的放置情况相同。
4. 如果当前位置(i-1, j)和(i, j)都没有放骨牌，那么dp[i][j] = dp[i-2][j] + 1，即当前位置的放置情况是在前两行的放置情况基础上加1。

最终，dp[N][M]即为最多能放的骨牌数量。

下面是C++的实现代码：

#include <iostream>
#include <vector>

using namespace std;

int maxDomino(int N, int M) {
    vector<vector<int>> dp(N+1, vector<int>(M+1, 0));

    for (int i = 2; i <= N; i+=2) {
        dp[i][0] = dp[i-2][0] + 1;
    }

    for (int i = 2; i <= M; i+=2) {
        dp[0][i] = dp[0][i-2] + 1;
    }

    for (int i = 2; i <= N; i+=2) {
        for (int j = 2; j <= M; j+=2) {
            dp[i][j] = max(dp[i][j-1], dp[i-2][j]) + (dp[i-1][j-1] == dp[i][j-2] ? 0 : 1);
        }
    }

    return dp[N][M];
}

int main() {
    int N, M;
    cin >> N >> M;
    cout << maxDomino(N, M) << endl;
    return 0;
}

在这个实现中，我们使用一个二维数组dp来保存每个位置的放置情况。首先，我们对第一行和第一列进行初始化，然后按行遍历更新dp数组。最后，返回dp[N][M]即为最多能放的骨牌数量