CppCPU占用时长 100秒内存使用限制 128MB题目描述从 11 到 �N 的整数中挑选一些数组成集合的方案数是可算的。如果加上 �M 个限制：某 22 个数不能同时选又要怎样计算？输入格式第一行包含 22 个整数 �N 和 �M下面 �M 行每行 22 个不同的整数 �a 和 �b 表示这 2 个数不能同时选。1≤��≤�1≤ab≤N有些限制可能出现多次。输出格式一个整数。

这道题目需要计算从1到N的整数中挑选一些数，组成集合的方案数，同时要满足M个限制：某两个数不能同时选。

可以使用动态规划的思想来解决这个问题。

首先，定义一个数组dp，dp[i]表示从1到i的整数中挑选一些数，组成集合的方案数。

根据题目要求，某两个数不能同时选，可以使用一个二维数组forbid来记录这些限制。forbid[a][b]表示a和b不能同时选。

然后，我们可以使用一个for循环来遍历从1到N的整数，对于每一个整数i，计算dp[i]的值。

对于dp[i]的计算，分两种情况讨论：

1. 如果i没有被限制，即不存在forbid[i][j]为true的j，那么dp[i]的值等于dp[i-1]，即从1到i-1的整数中挑选一些数，组成集合的方案数。

2. 如果i被限制，即存在forbid[i][j]为true的j，那么dp[i]的值等于dp[i-1]加上dp[j-1]，即从1到i-1的整数中挑选一些数，组成集合的方案数，再加上从1到j-1的整数中挑选一些数，组成集合的方案数。

最后，输出dp[N]的值即为所求的结果。

以下是一个示例的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<bool>> forbid(N + 1, vector<bool>(N + 1, false));
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        forbid[a][b] = true;
        forbid[b][a] = true;
    }

    vector<int> dp(N + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= N; i++) {
        if (!forbid[i][i - 1]) {
            dp[i] = dp[i - 1];
        } else {
            for (int j = 1; j < i; j++) {
                if (!forbid[i][j]) {
                    dp[i] += dp[j - 1];
                }
            }
            dp[i] += dp[i - 1];
        }
    }

    cout << dp[N] << endl;

    return 0;
}

该代码通过动态规划的方式计算了从1到N的整数中挑选一些数，组成集合的方案数，并考虑了M个限制的情况。最后输出结果