题解 P4728 [HNOI2009]双递增序列
lklklklklkl
·
·
题解
根据题目要求，容易发现我们得到的两个序列中是不能有任何逆序对的。考虑把原序列建成一张图，若原序列中 a_i 和 a_j 满足：
于是题目就被转化成：把一张图分成结点数相同的两部分，每一部分内部没有边相连。
自然地考虑到二分图。若建出来的图不是二分图，则原序列一定不符合要求；若建出来的图是二分图，那么考虑将图中的每个连通块进行染色，分别记下每个连通块中被染成两种不同颜色的结点数。容易得知，要得出两个符合要求的子序列，必须存在一种方案，在每个连通块中取出一种颜色的结点，使得取出的所有结点数之和为 $\dfrac n2$。直接 dp 即可。
Code：
```cpp
//sxy bless pr
#include<bits/stdc++.h>
using namespace std;
int n,a[2005];
vector<int> e[2005];
int c[2005];
int cl[2005],now;
bool f[2005][4005];
bool dfs(int x,int co){
if(c[x]) return true;
c[x]=co;
cl[co]++;
bool flag=true;
for(int i=0;i<e[x].size();i++){
if(!c[e[x][i]]){
flag=(dfs(e[x][i],now*2+1-co)&&flag);
}
else if(c[e[x][i]]==c[x]) return false;
}
return flag;
}
void solve(){
scanf("%d",&n);
memset(c,0,sizeof(c));
memset(cl,0,sizeof(cl));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) e[i].clear();
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]>=a[j]){
e[i].push_back(j);e[j].push_back(i);
}
}
}
now=1;
for(int i=1;i<=n;i++){
if(!c[i]){
if(!dfs(i,now)){
puts("No!");
return;
}
now+=2;
}
}
memset(f,0,sizeof(f));
f[1][cl[1]]=f[1][cl[2]]=1;
for(int i=3;i<=now;i+=2){
for(int j=0;j<=n;j++){
f[i][j+cl[i]]|=f[i-2][j];
f[i][j+cl[i+1]]|=f[i-2][j];
}
}
if(f[now][n/2]) puts("Yes!");
else puts("No!");
}
int main(){
int m;
cin>>m;
for(int i=1;i<=m;i++) solve();
}
```