Description
给定一个长度为N（N为偶数）的序列，问能否将其划分为两个长度为N/2的严格递增子序列，
Input
若干行，每行表示一组数据。对于每组数据，首先输入一个整数N，表示序列的长度。之后N个整数表示这个序列。
Output
同输入行数。对于每组数据，如果存在一种划分，则输出“Yes!”，否则输出“No!“。
Sample Input
6 3 1 4 5 8 7
6 3 2 1 6 5 4
Sample Output
Yes!
No!
HINT
共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9
第一组(30%)：N <= 20
第二组(30%)：N <= 100
第三组(40%)：N <= 2000
题解
在前$i$位中找长$j$位的以第$i$位结尾的上升子序列（我们设这个为序列$A$），并且剩下的也是上升子序列（设这个为序列$B$），那么$f[i][j]$表示剩下的（即前i位中长$i-j$位的不以第$i$位结尾的）上升子序列（即序列$B$）的最后一位的最小值。
注意：$A$一定是以最后一个数结尾的。
然后转移：
如果$a[i]<a[i+1]$，那么$f[i+1][j+1] = min(f[i+1][j+1], f[i][j])$，意思就是将$a[i+1]$接在序列$A$后，相当于可以直接把$f[i][j]$扩展到第$i+1$位。
如果$f[i][j]<a[i+1]$，那么$f[i+1][i-j+1] = min(f[i+1][i-j+1], a[i])$，意思是将$a[i+1]$接在$B$后，相当于第$i+1$继承前$i$位中$i-j$位长的上升子序列，此时$B$序列的某尾为最后一个数，那么我们就要$swap(A,B)$。
//It is made by Awson on 2017.9.27
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define LL long long
using namespace std;
const int N = ;
void read(int &x) {
char ch; bool flag = ;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());
for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());
x *= -*flag;
} int n, a[N+];
int f[N+][N+]; void work() {
for (int i = ; i <= n; i++)
read(a[i]);
memset(f, , sizeof(f));
int INF = f[][];
f[][] = -;
for (int i = ; i <= n; i++)
for (int j = ; j <= i; j++)
if (f[i][j] != INF) {
if (a[i] < a[i+]) f[i+][j+] = Min(f[i+][j+], f[i][j]);
if (f[i][j] < a[i+]) f[i+][i+-j] = Min(f[i+][i+-j], a[i]);
}
printf(f[n][n/] == INF ? "No!\n" : "Yes!\n");
}
int main() {
while (~scanf("%d", &n))
work();
return ;
}