Luogu P4728 [HNOI2009]双递增序列题解

type

Post

status

Published

date

Mar 13, 2023

slug

summary

难度：省选/NOI-

[HNOI2009]双递增序列

题目描述

考虑一个长度为偶数的序列，我们称这个序列为好的，当且仅当存在的一个划分，且。

比如序列就是一个好的序列。因为它可以分成。而序列则不是一个好的序列。

现在的问题是，针对给出的若干序列，请你判断它们是否是好的序列。

输入格式

第一行仅包含一个整数，表示需要判断个序列。接下来的行分别给出这些序列。每个序列的输入为一行，每行的第一个数为一个偶数，表示序列的长度，随后的个整数表示序列本身的元素。同一行的各数之间用一个空格隔开。

输出格式

输出行，如果第个序列为好的序列，那么第行输出Yes!，否则输出 No!。

样例 #1

样例输入 #1


2
6 3 1 4 5 8 7
6 3 2 1 6 5 4

样例输出 #1


Yes!
No!

提示

对于的数据，。对于的数据，。对于的数据，，，。

题意分析

简单来说：判断给定序列能否分成两个递增序列，并且序列长度相等。

很明显< 不是偏序关系，于是无法使用迪尔沃斯定理。

考虑到对于每一个数，只能添加到两个序列中的某一个的后面，数据范围也比较小，可以考虑二维dp解决。

对于第一个维度，可以考虑两个序列中的某个序列的最后一个元素，就是输入序列的这个数；对于第二个维度，可以考虑为这个序列的长度；dp的值可以表示另一个序列的最后一个元素的最小值，于是可以同时表示两个序列的最后的值。用形式化语言描述为：中的表示两个序列中共有个元素，表示最后一个元素是的序列的长度为，表示另一个序列的最后一个元素的最小值。

只有当前输入值，比之前的某个序列的最后一个值大的时候，才能更新dp，对于两个序列，可以得到两个状态转移方程：

加到相同的序列

加到不同的序列

最后只需要判断是否存在即可。

考虑状态初始化：

表示另一个序列为空，则其最小值可以看作负无穷；

再考虑 , 其值必然是 ;

再考虑 , 另一个序列为空，负无穷；如果此项存在还需要 ;

在的情形，均可以通过状态转移方程得到。

代码


#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int maxn = 2e3 + 3;

int arr[maxn];
int dp[maxn][maxn]; // i 表示其中一个序列最后一个数是a[i], j 表示其长度，dp[i][j],表示另一个序列最后一个元素最小值；
void solve() {
	memset(dp, 0x3f3f3f3f, sizeof dp);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	// 首先考虑初始化情形：dp[1][1]表示另一个序列为空，则其最小值可以看作负无穷；
	// 再考虑 dp[2][1], 其值必然是arr[1];
	// 再考虑 dp[2][2], 另一个序列为空，负无穷； 如果此项存在还需要 arr[2] > arr[1];
	// 考虑到只有当前元素大于上一个元素，才能使加到当前序列后面
	// 只有当前元素大于另一个序列的最小值，才能加到上一个序列的后面
	dp[1][1] = -0x3f3f3f3f;
	dp[2][1] = arr[1];
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= min(i, n / 2); j++) {
			// arr[i]加到dp[i-1][j-1]相同的序列
			if (arr[i] > arr[i - 1]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
			// arr[i]加到dp[i-1][i-j]不同的序列
			if (arr[i] > dp[i - 1][i - j]) dp[i][j] = min(dp[i][j], arr[i - 1]);
		}
	}
	cout << (dp[n][n / 2] == 0x3f3f3f3f ? "No!" : "Yes!") << endl;
}

int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	while (n--) {
		solve();
	}
}