P2766 最长不下降子序列问题

题解：用最莽的方法求出最长不下降子序列，然后以i为最后一个节点长度为1的与源点连容量为1的边，长度为最长公共子序列的与汇点连容量为1的边，拆点控制每个点选一次，求最大流得出问题二。对于问题三，将源点与1，1与拆点n+1,源点与n,n与n+n,n+n与汇点容量变为正无穷，在问题二的残余网络跑最大流即可。

  1 #include
  2 using namespace std;
  3 const int N=1010,M=(2*N+25e5)*2,inf=1e9;
  4 int h[N],f[M],ne[M],e[M],idx;
  5 int cur[N],d[N],a[N],dp[N];
  6 int n,S,T;
  7 void add(int a,int b,int c)
  8 {
  9     ne[idx]=h[a],e[idx]=b,f[idx]=c,h[a]=idx++;
 10     ne[idx]=h[b],e[idx]=a,f[idx]=0,h[b]=idx++;
 11 }
 12 bool bfs()
 13 {
 14     memset(d,-1,sizeof d);
 15     queue<int>q;
 16     q.push(S);
 17     d[S]=0;
 18     cur[S]=h[S];
 19     while(q.size())
 20     {
 21         int t=q.front();
 22         q.pop();
 23         for(int i=h[t];i!=-1;i=ne[i])
 24         {
 25             int j=e[i];
 26             if(d[j]==-1&&f[i])
 27             {
 28                 d[j]=d[t]+1;
 29                 cur[j]=h[j];
 30                 if(j==T)return true;
 31                 q.push(j);
 32             }
 33         }
 34     }
 35     return false;
 36 }
 37 int find(int u,int limit)
 38 {
 39     if(u==T)return limit;
 40     int flow=0;
 41     for(int i=cur[u];i!=-1&&flowne[i])
 42     {
 43         int j=e[i];
 44         cur[u]=i;
 45         if(d[j]==d[u]+1&&f[i])
 46         {
 47             int t=find(j,min(f[i],limit-flow));
 48             if(!t)d[j]=-1;
 49             f[i]-=t,f[i^1]+=t,flow+=t;
 50         }
 51     }
 52     return flow;
 53 }
 54 int dinic()
 55 {
 56     int r=0,flow;
 57     while(bfs())while(flow=find(S,inf))r+=flow;
 58     return r;
 59 }
 60 int main()
 61 {
 62     memset(h,-1,sizeof h);
 63     cin>>n;
 64     S=0,T=2*n+1;
 65     for(int i=1;i<=n;i++)
 66     scanf("%d",&a[i]);
 67     for(int i=1;i<=n;i++)
 68     add(i,n+i,1);
 69     int s=0;
 70     for(int i=1;i<=n;i++)
 71     {
 72         dp[i]=1;
 73         for(int j=1;j)
 74         {
 75             if(a[j]<=a[i])
 76             {
 77                 dp[i]=max(dp[i],dp[j]+1);
 78             }
 79         }
 80         for(int j=1;j)
 81         {
 82             if(a[j]<=a[i])
 83             {
 84              if(dp[i]==dp[j]+1)
 85              add(n+j,i,1);
 86             }
 87         }
 88         s=max(s,dp[i]);
 89         if(dp[i]==1)
 90         add(S,i,1);
 91     }
 92     printf("%d\n",s);
 93     if(s==1)printf("%d\n%d\n",n,n);
 94     else
 95     {
 96     for(int i=1;i<=n;i++)
 97     if(dp[i]==s)add(i+n,T,1);
 98     int res=dinic();
 99     printf("%d\n",res);
100     for(int i=0;i2)
101     {
102         int a=e[i^1],b=e[i];
103         if(a==S&&b==1)f[i]=inf;
104         if(a==1&&b==n+1)f[i]=inf;
105         if(a==S&&b==n)f[i]=inf;
106         if(a==n&&b==n+n)f[i]=inf;
107         if(a==n+n&&b==T)f[i]=inf;
108         if(a==1+n&&T==b)f[i]=inf;
109     }
110     res+=dinic();
111     printf("%d\n",res);
112 }
113 }