题解：P1410 子序列

StarsIntoSea · 2025-11-27 09:10:26 · 题解

很神的一道 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)。

#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();
}