Problem Link

[HNOI2009] 双递增序列

题目描述

给定一个长度为 \(n\) 的序列（\(n\) 为偶数），求是否可以把序列分成 \(2\) 个长度为 \(\frac{n}{2}\) 的递增序列。

Solution

首先想到定义 \(f_i\) 为一个序列以 \(a_i\) 结尾时另一个序列末尾最小值。

但这样定义状态信息是不够的，考虑再加一维。

定义 \(f_{i, j}\) 为 \(s\) 序列以 \(a_i\) 结尾， \(t\) 序列长度 \(j\) 时末尾最小值。

显然，若设所有 \(f_{i, j}\) 初值为 \(+\infin\)，若 \(f_{n, \frac{n}{2}} \ne +\infin\) 则存在分解方法，反之则没有。

如何转移呢？

• \(a_{i-1} < a_i\)：则 \(a_i\) 可以放入任意序列中，\(f_{i, j} = \min{f_{i, j+1}, f_{i-1, j}}\)。

• \(f_{i-1, j} < a_i\)：则 \(a_i\) 可以放入 \(t\) 序列中，\(f_{i, i-j} = \min{f_{i, i-j}, a[i-1]}\)。

优雅的状态转移，华丽收场。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define Maxn 2005
#define Inf 0x7fffffff
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

int n, a[Maxn], f[Maxn][Maxn];

int main()
{
    int _ = read();
    while(_--)
    {
        n = read();
        fo(i, 1, n) a[i] = read();
        fo(i, 1, n) fo(j, 1, n) f[i][j] = Inf;
        f[1][0] = 0, f[1][1] = -Inf;
        fo(i, 1, n)
        {
            fo(j, 1, min(n/2, i))
            {
                if(a[i] > a[i-1]) f[i][j+1] = min(f[i][j+1], f[i-1][j]);
                if(f[i-1][j] < a[i]) f[i][i-j] = min(f[i][i-j], a[i-1]);
            }
        }
        if(f[n][n/2] == Inf) puts("No!");
        else puts("Yes!");
    }
    return 0;
}

Tips

记得赋初值！