网络流
最多不相交路径，网络最大流

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#define MAXX 502
#define MAXM 502*502+1001
#define INF 9999999
using namespace std;

struct se{
  int nxt,to,c;
}e[MAXM*4];

int n,m,a[MAXX+1],f[MAXX+1],tot,head[MAXX+1],deep[MAXX+1],all;
 
void add(int from,int to,int w){
  e[tot].nxt=head[from];
  e[tot].to=to;
  e[tot].c=w;
  head[from]=tot++;
}
void ADD(int from,int to,int w){
  add(from,to,w);
  add(to,from,0);
}
void DP(){
  f[1]=1;
  for(int i=2;i<=n;++i){
    for(int j=i-1;j;j--){
      if(f[j]>f[i]&&a[j]<=a[i])
    f[i]=f[j];
    }f[i]++;
  }for(int i=1;i<=n;++i)all=max(all,f[i]);
  printf("%d\n",all);
}
bool BFS(int s,int t){
  queue<int>que;
  while(!que.empty())que.pop();
  for(int i=1;i<=n+2;++i)deep[i]=0;
  que.push(s),deep[s]=1;
  while(!que.empty()){
    int u=que.front();
    for(int i=head[u];i!=-1;i=e[i].nxt)if(!deep[e[i].to]&&e[i].c){
    int v=e[i].to;
    deep[v]=deep[u]+1;
    que.push(v);
    if(v==t)return 1;
      }
    que.pop();
  }return 0;
}
int dinic(int s,int t,int T){
  if(s==t)return T;int tag=0;
  for(int i=head[s];i!=-1;i=e[i].nxt)if(e[i].c&&deep[e[i].to]==deep[s]+1){
      int d=dinic(e[i].to,t,min(T,e[i].c));
      e[i].c-=d,e[i^1].c+=d;tag+=d;
      if(tag==T)return tag;
    }return tag;
}
void flow1(){
  for(int i=1;i<=n;++i)if(f[i]==1)ADD(0,i,1);
  for(int j=2;j<=n;++j){
    if(f[j]==all)ADD(j,n+1,1);
    for(int i=1;i<j;++i)
      if((f[i]+1==f[j])&&a[i]<=a[j])
    ADD(i,j,1);
  }
  int ans=0;
  while(BFS(0,n+1))ans+=dinic(0,n+1,INF);
  if(all!=1)
  printf("%d\n",ans);
  else cout<<ans+1<<‘\n‘;
}
void flow2(){
  memset(e,0,sizeof(e));tot=0;
  memset(head,-1,sizeof(head));
  for(int i=1;i<=n;++i)if(f[i]==1)ADD(0,i,INF);
  for(int j=2;j<=n;++j){
    if(f[j]==all)ADD(j,n+1,INF);
    for(int i=1;i<j;++i)
      if((f[i]+1==f[j])&&a[i]<=a[j])
    ADD(i,j,1);
  }
  int ans=0;
  while(BFS(0,n+1))ans+=dinic(0,n+1,INF);
  printf("%d\n",ans);
}
int main(){
  memset(head,-1,sizeof(head));
  scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%d",&a[i]);
  DP();
  if(all!=1)flow1(),flow2();
  if(all==1)flow1(),flow1();
  return 0;
}