其实这题很容易设出四维的 $\rm{DP}$ ,也就是用 $dp_{i,j,x,y}$ 表示第一个序列的终止位置为 $i$ 且长度为 $x$,第二个序列的终止位置为 $j$ 且长度为 $y$ 是否成立 ,然后也很容易想到降维,枚举当前序列长度 $len$ 的时候知道了 $x$ 就已经知道 $y$ 了—— $y$ 就是 $len-x$ 。也就是说现在的 $DP$ 是 $O(n^3)$ 的,还需要优化。

考虑设 $dp_{i,j}$ 表示第一个序列的最终位置为 $i-1$ 且长度为 $j$ 时第二个序列的最终位置的最小值。枚举当前数字 $i$ ,然后分两种情况进行转移——将 $a_i$ 放到第一个序列末尾 $\texttt{and}$ 将 $a_i$ 放到第二个序列末尾。

放到第一个序列末尾很好想:因为当前第一个序列的结尾处就是 $a_{i-1}$ ,比较一下大小直接转移就好了:

$$dp_{i,j}=min(dp_{i,j},dp_{i-1,j-1}) \ \ \ (a_i>a_{i-1})$$

因为第二个序列的末尾没变,所有直接转移就好。

接下来考虑将第 $i$ 个数放到第二个序列末尾的情况,其实第一个序列和第二个序列没区别,当然除了名字上有一个字的差异,假设第 $i-1$ 个数是第二个序列末尾,当前第一个序列的长度为 $j-1$ ,那么第二个序列的长度因该就是 $(i-1)-(j-1)$ 了,因为我们假设了第 $i-1$ 个数是第二个序列末尾,那么 $dp_{i-1,i-j}$ 又可以被解释为第二个序列的末尾为 $i-1$ 个数且第二个序列的长度为 $i-j$ 的时候第一个序列的末尾的最小值 ,如果这个最小值小于 $a_i$ ,说明 $a_i$ 可以接到第一个序列前面,那么这个时候第二个序列的末尾为 $a_{i-1}$ ,显然又有转移:

$$dp_{i,j}=min(dp_{i,j},a_{i-1}) \ \ \ (a_i>dp_{i-1,i-j})$$

开始的时候我们将 $dp$ 数组赋成极大值,然后最后判断一下 $dp_{n,n/2}$ 这个状态变小没有就好。

Code:

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=2e3+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int a[N],f[N][N];
int solve() {
    int n;IN(n);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i) IN(a[i]);
    a[0]=f[0][0]=-1;
    for(int i=1;i<=n;++i) {
        f[i][0]=a[i];
        for(int j=1;j<=i&&j<=n/2;++j) {
            if(a[i]>a[i-1]) f[i][j]=min(f[i][j],f[i-1][j-1]);
            if(a[i]>f[i-1][i-j]) f[i][j]=min(f[i][j],a[i-1]);
        }
    }return f[n][n/2]<0x3f3f3f3f;
}

int main() {
    int T;IN(T);
    while(T--) puts(solve()?"Yes!":"No!");
    return 0;
}

感觉这道题的确很绕......=。=

最后修改:2019 年 05 月 30 日 03 : 23 PM