SSLOJ 1488.上升子序列【dp】【思维】【二分图匹配】

题意：

给一个长度为 $n$的数组 $a$。试将其划分为两个严格上升子序列，并使其长度差最小

分析：

我们将点对 $(i,j)$，当 $i < j$且 $a_i \geqslant a_j$时我们将两点连线，跑一遍二分图匹配，以得到的联通块跑分组背包
但我们会发现这样铁 $T$，所以我们继续加深思考 $($以高度表示数的大小 $)$，对于满足条件的 $i,j$来说，它们之前的某个位置 $k$的性质 $：$无论 $a_k$的大小如何，始终都会和至少 $i$或 $j$的一个连线

这就启示我们只需要找到 $i,j$就好了，它们两个之间的区间必是一个连通块
而对于不同的联通块，我们会发现，前面的联通的最大值，一定会小于后面任意联通块的最小值，根据这个性质，我们就可以记录前缀最大值和后缀最小值，以此来确定每个区间的分界点
然后对于每个区间暴力判断是否合法
因为每个区间有且仅有一种合法的分配方案，所以我们对于每个区间同时记录一个 $z_i$表示该区间的数分成两个序列的长度差
设 $f_{i,j}$表示到第 $i$个联通块时两个序列长度差为 $j$， $0/1$表示这种长度差是否可能，那么会有方程 $:$在这里插入代码片
$f_{i,j}=f_{i-1,|j+z_i|}\ |\ f_{i-1,|j-z_i|}$

代码：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#define LL long long 
using namespace std;
inline LL read() {LL d=0,f=1;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}return d*f;
}
int z[100005],mi[100005],ma[100005],a[100005];
int q[100005],cnt=0;
int f[2][200005];
int main()
{int t=read();while(t--){cnt=0;int n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) ma[i]=max(ma[i-1],a[i]);mi[n+1]=2147483647; for(int i=n;i;i--) mi[i]=min(mi[i+1],a[i]); cnt=0;for(int i=1;i<=n;i++) if(ma[i]<=mi[i+1]) q[++cnt]=i;int s1,s2,d1,d2;int tf=0;for(int i=1;i<=cnt;i++){s1=0;s2=0;d1=0;d2=0;for(int j=q[i-1]+1;j<=q[i];j++) {if(a[j]>s1) s1=a[j],d1++;else if(a[j]>s2) s2=a[j],d2++;else {tf=1;break;}}if(tf) break;z[i]=abs(d1-d2);}if(tf) {printf("-1\n");continue;}memset(f,0,sizeof(f));f[0][0]=1;for(int i=1;i<=cnt;i++)for(int j=0;j<=n;j++)f[i&1][j]=f[~i&1][abs(j-z[i])]|f[~i&1][abs(j+z[i])];for(int i=0;i<=n;i++) if(f[cnt&1][i]) {printf("%d\n",i);break;}}return 0;
}