C++ 解题：最长上升子序列长度为 n-1 的排列计数

{"title":"用C++讲解以下题目：\nMX 在研究排列所具有的性质。这一天，她拿出了 \nn 张卡片排成一排，想要在上面填数以写成一个 \n1\n∼\nn 的排列。\n\nPiggy 趁 MX 不注意，偷偷在一些卡片上写了数。\n\n题目描述\nMX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 \nn−1\nn−1，MX 有多少种填数方法呢？\n\nPiggy 比较良心。他没有在不同的位置上填相同的数。\n\n输入格式\n本题有多组测试数据。\n\n第一行一个整数 \nT 代表数据组数。\n对于每组数据：\n\n第一行两个整数 \nn,q 代表卡牌个数和 Piggy 已经填上了多少个数。\n第二行 \n2q 个整数，第 \n2i−1,2i 个整数 \n(x,y)\n(x,y) 代表第 \nx 个数被 Piggy 填成了 \ny。\n输出格式\n输出 \nT 行，每行一个整数代表答案。\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−1\n−1 代表此位置数字还未确定。\n样例 \n1\n1：第一组给定的排列为 \n−1\n,2,−1,8,−1,5,6,−1,−1,−1\n−1,2,−1,8,−1,5,6,−1,−1,−1。容易发现，只有 \n1,2,3,8,4,5,6,7,9,10\n1,2,3,8,4,5,6,7,9,10 的最长上升子序列长度为 \n10−1=9\n10−1=9。第二组给定的排列为 \n−1\n,−1\n−1,−1，2,1\n2,1 为唯一满足要求的序列。\n\n本题采用捆绑测试。\n\nSubtask\n∑\nT∑n\n∑\nq∑q\n分值\n0\n≤\n10\n≤10\n≤\n10\n≤10\n10\n1\n≤\n15\n≤15\n≤\n10\n≤10\n20\n2\n≤\n5\n×\n10\n3\n≤5×10 \n3\n \n≤\n5\n×\n10\n3\n≤5×10 \n3\n \n30\n3\n≤\n5\n×\n10\n5\n≤5×10 \n5\n \n≤\n5\n×\n10\n5\n≤5×10 \n5\n \n40\n保证 \n0\n≤\nq\n≤\nn\n0≤q≤n，\n1\n≤\nn\n≤\n5\n×\n10\n5\n1≤n≤5×10 \n5\n ，\n1\n≤\nT\n≤\n10\n5\n1≤T≤10 \n5\n ，\n1\n≤\nx,y\n≤\nn\n1≤x,y≤n。\n备注：避免运行超时内容：首先，我们需要知道最长上升子序列的定义。一个序列中的最长上升子序列是指序列中一些元素按照原有的顺序排列，并且满足元素的值逐渐增大。例如，序列[1, 3, 2, 4, 5]中的最长上升子序列为[1, 2, 4, 5]，长度为4。\n\n根据题目要求，我们需要填入一些数使得原序列仍然是一个排列，并且最长上升子序列的长度为n-1。假设原序列为A，我们需要填入的数为B。那么A和B合并后的序列的最长上升子序列长度应该为n-1。\n\n我们可以通过动态规划的方法来解决这个问题。定义一个数组dp，dp[i]表示以第i个数结尾的最长上升子序列的长度。初始时，dp[i]都为1，表示以第i个数结尾的最长上升子序列长度至少为1。\n\n然后，我们遍历数组A中的每个数，计算dp[i]的值。对于每个dp[i]，我们需要找到它之前的所有dp[j]，其中j < i，且A[j] < A[i]，然后更新dp[i]的值为dp[j]+1中的最大值。即：\n\ndp[i] = max(dp[j]+1)，其中j < i，且A[j] < A[i]\n\n最后，我们遍历dp数组，找到最大的dp[i]，即为最长上升子序列的长度。如果最长上升子序列的长度为n-1，说明填入的数B满足条件。否则，填入的数B不满足条件。\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\n vector<int> A(n+1);\n vector<int> dp(n+1, 1);\n\n for (int i = 1; i <= 2*q; i += 2) {\n int x, y;\n cin >> x >> y;\n A[x] = y;\n }\n\n for (int i = 2*q+1; i <= n; i++) {\n A[i] = -1; // 未填入的数用-1表示\n }\n\n for (int i = 2; i <= n; i++) {\n for (int j = 1; j < i; j++) {\n if (A[j] < A[i]) {\n dp[i] = max(dp[i], dp[j]+1);\n }\n }\n }\n\n int longest = *max_element(dp.begin(), dp.end());\n if (longest == n-1) {\n cout << "1" << endl;\n } else {\n cout << "0" << endl;\n }\n }\n\n return 0;\n}\n\n\n该算法的时间复杂度为O(n^2)，其中n为卡牌的个数。