洛谷P1410 子序列 题解

题目链接：P1410 子序列

题意：

给定一个长度为 $N$（$N$ 为偶数）的序列，问能否将其划分为两个长度为 $N / 2$ 的严格递增子序列。

【数据范围】

共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9

第一组(30%)：N <= 20

第二组(30%)：N <= 100

第三组(40%)：N <= 2000

首先可以有个原始的思路

设 $f_{i,j,k}$ 表示前 $i$ 位，以 $i$ 结尾的上升子序列长度为 $j$ ，另一个上升子序列以 $k$ 结尾是否可行。

如果仅仅用是否可行去做，比较浪费。

注意到我们一定希望 $a_k$ 尽可能小，这个很好用dp去算

考虑把 $k$ 这一维去掉，移到 $f$ 里让它算。

设 $f_{i,j}$ 表示以 $i$ 结尾的上升子序列长度为 $j$ ，不以 $i$ 结尾的另一条上升子序列的结尾的最小值。

如果 $a_i < a_{i+1}$ ，那么 $a_{i+1}$ 可以被加入以 $i$ 结尾的上升子序列

$$f_{i+1,j+1}=\min\{f_{i+1,j+1},f_{i,j}\}$$

如果 $f_{i,j}<a_{i+1}$ ，那么 $a_{i+1}$ 可以被加入不以 $i$ 结尾的上升子序列

注意此时如果加入不以 $i$ 结尾的上升子序列更优的话，

• 不以 $i$ 结尾的那个子序列变成了以 $i+1$ 结尾的子序列
• 以 $i$ 结尾的那个子序列变成了不以 $i+1$ 结尾的子序列

$$f_{i+1,i-j+1}=\min\{f_{i+1,i-j+1},a_i\}$$

时间复杂度 $O(Qn^2)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)

int n,a[N],f[N][N];
void clear()
{
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            f[i][j]=INF;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n)
    {
        clear();
        for(int i=1; i<=n; i++) cin >> a[i];
        f[1][1]=-1;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=i; j++)
            if(f[i][j]!=INF)
            {
                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]);
            }
                    
        cout << (f[n][n/2]!=INF?"Yes!\n":"No!\n");
    }
    return 0;
}