题解：P1410 子序列

很神的一道 DP！！

捋一下我们需要的状态：

第一个子序列的当前末尾元素。
第二个子序列的当前末尾元素。
第一个子序列的长度。
第二个子序列的长度。

但是

n\le2000

，需要考虑优化。

假设枚举到了第

a_i

时，前

i-1

已经被分配完，那么这两个子序列的长度之和等于

i-1

。这样就只需要记录其中一个子序列的长度即可。

发现如果枚举到了第

a_i

，那么

a_{i-1}

一定在其中一个子序列的末尾。这样就只需要记录另一个子序列的末尾元素即可，如果另一个子序列的长度不变，我们要希望这个子序列的末尾尽可能小。

设状态

f(i,j)

表示分配完了前

i

个元素，其中末尾为

a_i

的子序列的长度为

j

时，另一个子序列的末尾为

f(i,j)

。显然另一个子序列的长度为

i-j

，这样就能用二维表示四个状态。

如果不能分配，

f(i,j)

就表示正无穷。

转移就是：

如果 $a_i>a_{i-1}$ ，那么 $f(i,j) \leftarrow f(i-1,j-1)$ 。相当于插入末尾是 $a_{i-1}$ 的子序列中。
如果 $a_i>f(i-1,j)$ ，那么 $f(i,i-j) \leftarrow a_{i-1}$ 。相当于插入末尾不是 $a_{i-1}$ 的子序列中。

时间复杂度

O(n^2)

。

CPP

#include <bits/stdc++.h>
using namespace std;
const int N=2005;
int f[N][N];
int n,a[N];
void sol(){
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	memset(f,0x7f,sizeof f);
	f[0][0]=a[0]=-1;
	for(int i=1;i<=n;++i){
		if(a[i-1]<a[i]) for(int j=1;j<=i;++j)
			f[i][j]=f[i-1][j-1];
		for(int j=1;j<i;++j) if(f[i-1][j]<a[i])
			f[i][i-j]=min(f[i][i-j],a[i-1]);
	}
	puts(f[n][n/2]>1e9?"No!":"Yes!");
}
int main(){
	while(scanf("%d",&n)==1) sol();
}

题解：P1410 子序列

文章操作

相关推荐

评论

题解：P1410 子序列