Discription

给定长度为 $n$ 的序列 $A$（$n$ 为偶数），判断是否能将其划分为两个长度为 $\dfrac{N}{2}$ 的严格递增子序列。

Solution

不妨按下标从小到大考虑每个数要分给哪一组，比较明显的 DP，朴素时空复杂度太高。

在朴素中，我们需要知道四个信息：

第一组的长度
第一组最后一个数的数值
第二组的长度
第二组最后一个数的长度

由于所有数都得填，所以当填完前 $i$ 个数的时候，肯定有一组的末尾是 $A[i]$，可以降一个维度
考虑把可行性 DP，把一个状态，用贪心最优性搞在状态里，这题的最后一个数的数值显然越小越好（容错率越高）。

这样状态数量就在两维了，每次转移其实就是考虑这个数到两个组中的哪一个，应该是可以接受的。

状态设计

设 $f_{i, j}$ 为填完了前 $i$ 个数，以 $a[i]$ 结尾的那组长度为 $j$，所能构成的另外一组最后一个数的的最小值。

状态转移

”我为人人“ 式转移可能更好理解：

考虑将 $A[i + 1]$ 填入以 $A[i]$ 结尾的组里，需要满足 $A[i] < A[i + 1] $，转移为 $f_{i + 1, j + 1} = \min(f_{i, j})$
将第 $A[i + 1]$ 填入另一组组里，需要满足 $f_{i, j} < A[i + 1]$，转移为 $f_{i + 1, i - j + 1} = \min(A[i])$

最后检测 $f_{n, n / 2}$是否等于无穷即可。

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N = 2005, INF = 0x3f3f3f3f;

int n, a[N], f[N][N >> 1];

int main() {

	while (~scanf("%d", &n)) {

		memset(f, 0x3f, sizeof f);

		for (int i = 1; i <= n; i++) scanf("%d", a + i);

		f[1][1] = -1;

		for (int i = 1; i < n; i++) {

			for (int j = 1; j * 2 <= n; j++) {

				if (f[i][j] == INF) continue;

				if (a[i] < a[i + 1]) f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);

				if (f[i][j] < a[i + 1]) f[i + 1][i - j + 1] = min(f[i + 1][i - j + 1], a[i]);

			}

		}

		puts(f[n][n / 2] != INF ? "Yes!" : "No!");

	}

	return 0;

}

巴特西

落谷 P1410 子序列

Discription

Solution

状态设计

状态转移

最新文章

热门文章