最长不下降子序列问题
sshwy
2019-03-03 09:11:34
# 题意
对一个序列做3个统计：
- 最长不下降子序列的长度$k$
- 每个数用一次，可以不用，最多能组成多少个长度为$k$的不下降子序列
- 在$Subtask2$的基础上，允许第一个数和最后一个数多次使用，求最多能组成多少个长度为$k$的不下降子序列
$n\leq 500$.
<!--more-->
# Subtask1
$O(n^2)$暴力DP即可，定义$f[i]$表示以$a_i$开头的最长不下降子序列的长度
$$
f[i]=\max_{j=i+1}^n\{f[j]+1\}.
$$
# Subtask2
构造网络流模型如下（c表示边的容量）
- 每个数只能使用一次$\Leftrightarrow $拆点$u_{in},u_{out}$，并添加$c(u_{in},u_{out})=1$.
- $f[u]=k\Leftrightarrow c(s,u_{in})=1$.
- $f[u]=1\Leftrightarrow c(u_{out},t)=1$.
- $u<v,a_u\leq a_v,f[u]=f[v]+1\Leftrightarrow c(u_{out},v_{in})=1$.
跑一遍最大流即可
# Subtask3
在$Subtask2$的基础上修改（或者直接加边）如下
- $c(n_{in},n_{out})=INF,c(n_{out},t)=INF$.
- $f[1]=k\Leftrightarrow c(s,1_{in})=INF,c(1_{in},1_{out})=INF$.
再跑一遍最大流即可
# 代码
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1200,M=300000,INF=0x3f3f3f3f;
int n,m,s,t,k;
int a[N],f[N];
struct qxx{int nex,t,v;};
qxx e[M];
int cnt=1,h[N],cur[N];
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void add_flow(int f,int t,int v){add_path(f,t,v),add_path(t,f,0);}
int rk[N];
bool bfs(){
queue<int> q;
memset(rk,0,sizeof(rk));
memcpy(cur,h,sizeof(cur));
q.push(s),rk[s]=1;
while(q.size()){
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
if(w&&!rk[v])rk[v]=rk[u]+1,q.push(v);
}
}
return rk[t];
}
int dinic(int u,int flow){
if(u==t)return flow;
int x,rest=flow;
for(int i=cur[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
if(!w||rk[v]!=rk[u]+1)continue;
x=dinic(v,min(w,rest));
if(x)e[i].v-=x,e[i^1].v+=x,rest-=x;
else rk[v]=0;
if(!rest)cur[u]=i;
}
if(rest)cur[u]=0;
return flow-rest;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//sbt1
for(int i=n;i>=1;i--){
for(int j=i+1;j<=n;j++)if(a[i]<=a[j])f[i]=max(f[i],f[j]);
k=max(k,++f[i]);
}
printf("%d\n",k);
//sbt2
s=0,t=n+n+2;
for(int i=1;i<=n;i++){
add_flow(i<<1,i<<1|1,1);
if(f[i]==k)add_flow(s,i<<1,1);
if(f[i]==1)add_flow(i<<1|1,t,1);//不要随便加else
for(int j=i+1;j<=n;j++)if(a[i]<=a[j]&&f[i]==f[j]+1)add_flow(i<<1|1,j<<1,1);
}
int maxflow=0;
while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i;
printf("%d\n",maxflow);
//sbt3
add_flow(n<<1,n<<1|1,INF);add_flow(n<<1|1,t,INF);
if(f[1]==k){add_flow(s,1<<1,INF);add_flow(1<<1,1<<1|1,INF);}
while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i;
printf("%d\n",maxflow);
return 0;
}
```