C++ 算法题解：最长上升子序列计数问题

{"title":"用C++讲解以下题目：\nMX 在研究排列所具有的性质。这一天，她拿出了 \n\t\tn 张卡片排成一排，想要在上面填数以写成一个 \n\t\t1\n\t\t∼\n\t\t\tn1∼n 的排列。\n\nPiggy 趁 MX 不注意，偷偷在一些卡片上写了数。\n\n题目描述\nMX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 \n\t\t\tn−1\n\tn−1，MX 有多少种填数方法呢？\n\nPiggy 比较良心。他没有在不同的位置上填相同的数。\n\n输入格式\n本题有多组测试数据。\n\n第一行一个整数 \n\t\tT 代表数据组数。\n对于每组数据：\n\n第一行两个整数 \n\t\t\n,q 代表卡牌个数和 Piggy 已经填上了多少个数。\n第二行 \n\t\t2q 个整数，第 \n\t\t2i−1,2i 个整数 \n\t\t(x,y)\n\t\t(x,y) 代表第 \n\tx 个数被 Piggy 填成了 \n\ty。\n输出格式\n输出 \n\t\tT 行，每行一个整数代表答案。\n\n输入输出样例\n输入 #1复制\n2\n10 4\n2 2 4 8 6 5 7 6\n2 0\n输出 #1复制\n1\n1\n输入 #2\n2\n40 21\n1 1 2 2 6 6 7 7 8 8 9 9 10 10 11 11 15 15 16 16 23 23 24 24 25 25 26 26 30 30 34 35 35 36 36 37 37 38 38 39 40 40\n40 15\n3 3 4 4 14 14 15 15 17 17 19 19 24 23 25 24 27 26 30 29 31 30 33 32 35 34 39 38 40 39\n输出 #2复制\n4\n4\n说明/提示\n样例解释\n用 \n\t\t−1\n\t\t−1 代表此位置数字还未确定。\n样例 \n\t\t1：第一组给定的排列为 \n\t\t−1,2,−1,8,−1,5,6,−1,−1,−1\n\t\t−1,2,−1,8,−1,5,6,−1,−1,−1。容易发现，只有 \n\t\t1,2,3,8,4,5,6,7,9,10\n\t\t1,2,3,8,4,5,6,7,9,10 的最长上升子序列长度为 \n\t\t10−1=9\n\t\t10−1=9。第二组给定的排列为 \n\t\t−1,−1\n\t\t−1,−1，\n\t\t2,1\n\t\t2,1 为唯一满足要求的序列。\n\n本题采用捆绑测试。\n\nSubtask \n∑\n\t\tn \n∑\n\t\tq 分值\n0 \n≤10\n≤10 \n≤10\n≤10 10\n1 \n≤15\n≤15 \n≤10\n≤10 20\n2 \n≤5×103\n≤5×10 3 \n≤5×103\n≤5×10 3 30\n3 \n≤5×105\n≤5×10 5 \n≤5×105\n≤5×10 5 40\n保证 \n\t\t0≤q≤n，\n\t\t1≤n≤5×105\n\t\t1≤n≤5×10 5 ，\n\t\t1≤T≤105\n\t\t1≤T≤10 5 ，\n\t\t1≤x,y≤n\n\t\t1≤x,y≤n。\n备注：避免答案错误内容：题目要求填数使得排列的最长上升子序列的长度为n-1。\n\n我们可以先将填数的位置标记为-1，表示该位置还没有填数。然后根据给定的已填数位置和对应的数值，更新标记数组。\n\n接下来，我们需要找到填数的位置，并填上对应的数字。由于题目要求填数的排列的最长上升子序列的长度为n-1，我们可以利用动态规划的思想来解决。\n\n我们定义一个dp数组，dp[i]表示以第i个位置结尾的最长上升子序列的长度。初始时，dp数组的所有元素都为1，因为每个位置单独成一个上升子序列的长度为1。\n\n然后我们遍历每个位置i，对于每个位置i，我们遍历它之前的每个位置j，如果第j个位置的数小于第i个位置的数，且dp[j]+1大于dp[i]，则更新dp[i]为dp[j]+1。\n\n最后，我们找到dp数组中的最大值，即为所求的最长上升子序列的长度。\n\n最后，我们可以得到填数的方法数为2^(n-1) - 最长上升子序列的长度的个数。\n\n下面是代码实现：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nint main() {\n int T;\n cin >> T;\n while (T--) {\n int n, q;\n cin >> n >> q;\n vector<int> cards(n, -1); // 标记数组，-1表示未填数\n for (int i = 0; i < q; i++) {\n int x, y;\n cin >> x >> y;\n cards[x-1] = y; // 将已填数的位置标记为对应的数值\n }\n \n vector<int> dp(n, 1); // 动态规划数组\n for (int i = 1; i < n; i++) {\n for (int j = 0; j < i; j++) {\n if (cards[j] != -1 && cards[i] != -1 && cards[j] < cards[i]) {\n dp[i] = max(dp[i], dp[j] + 1);\n }\n }\n }\n \n int maxLen = *max_element(dp.begin(), dp.end()); // 最长上升子序列的长度\n int ans = (1 << (n-1)) - maxLen; // 填数的方法数\n cout << ans << endl;\n }\n return 0;\n}\n\n\n时间复杂度分析：假设卡牌个数为n，已填数个数为q，则建立标记数组的时间复杂度为O(n)，动态规划求解最长上升子序列的时间复杂度为O(n^2)，找到最长上升子序列的长度的时间复杂度为O(n)，因此总的时间复杂度为O(n^2)。空间复杂度为O(n)。