自动搬运

查看原文

来自洛谷，原作者为

	Ryo_Yamada **

搬运于2025-08-24 22:03:02，当前版本为作者最后更新于2020-08-24 20:51:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题“思维难度极高，代码难度极低”。

这题的状态定义非常神仙，用我们老师的话来说就是转移的艺术qaq。

对于枚举过的前 $i$ 个元素，若分成 $2$ 个子序列，必定有一个子序列的末尾是 $A_i$。所以首先可以想到，对于 $dp_i$，表示前 $i$ 个元素已经枚举，有一个子序列的末尾是 $A_i$。

当然这些不够，再加一维：对于 $dp_{i,j}$，表示表示前 $i$ 个元素已经枚举，有一个子序列的末尾是 $A_i$，其中不包含 $A_i$ 的子序列长度为 $j$ ，则包含 $A_i$ 的子序列长度为 $i-j$，用 $dp_{i,j}$ 表示该子序列末尾的最小值。

这样，我们就用两维的状态表示出了四个信息，最终答案是 $dp_{n, \frac{n}{2}}$。

再考虑转移：

• $A_i < A_{i+1}$：此时将 $A_{i+1}$ 拼接在 $A_i$ 后面，转移方程： $dp_{i+1,j+1}=\min(dp_{i+1,j+1}, dp_{i,j})$。
• $dp_{i,j} < A_{i+1}$：此时将 $A_{i+1}$ 拼接在另一个序列上面。为符合我们对状态的定义，我们需交换两个序列。转移方程：$dp_{i+1,i-j+1}=\min(dp_{i+1,i-j+1}, a_i)$。

最后，$dp$ 数组初始值全部设为 $+\infty$，$dp_{1,1}=-\infty$，时间复杂度 $O(n^2)$。

$\text{Code}$：

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 2005; 

int T, n;
int a[N], dp[N][N];

int main() {
	cin >> T;
	while(T--) {
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) scanf("%d", a + i);
		memset(dp, 0x3f, sizeof dp);
		dp[1][1] = -inf;
		for(int i = 1; i < n; i++) {//由于我的转移是转移i+1，所以i<n。
			for(int j = 1; j <= min(n / 2, i); j++) {//剪去无用状态
				if(a[i] < a[i + 1]) dp[i + 1][j + 1] = min(dp[i][j], dp[i + 1][j + 1]);
				if(a[i + 1] > dp[i][j]) dp[i + 1][i - j + 1] = min(a[i], dp[i + 1][i - j + 1]);//转移
			}
		}
		if(dp[n][n / 2] == inf) puts("No!");
		else puts("Yes!");
	}	
	return 0;
}