洛谷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;
}