「luogu2766」最长不下降子序列问题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=510,M=251000,oo=2e9;
 4 int n,a[N],f[N],ss,tt;
 5 struct Edge{
 6     int from,to,flow,cap;
 7     Edge(int _from=0,int _to=0,int _flow=0,int _cap=0):from(_from),to(_to),flow(_flow),cap(_cap){}
 8 };
 9 Edge edge[M<<1];
10 int edge_tot,spe[10];
11 vector<int>point[N<<1];
12 void add_edge(int f,int t,int c){
13     edge[edge_tot]=Edge(f,t,0,c);
14     point[f].push_back(edge_tot++);
15     edge[edge_tot]=Edge(t,f,0,0);
16     point[t].push_back(edge_tot++);
17     return;
18 }
19 int level[N<<1];
20 bool bfs(){
21     memset(level,0,sizeof(level));
22     queue<int>q;
23     q.push(ss);
24     level[ss]=1;
25     int x;
26     while(!q.empty()){
27         x=q.front();q.pop();
28         for(int i=0;i<point[x].size();i++){
29             Edge& e=edge[point[x][i]];
30             if(e.cap>e.flow&&!level[e.to]){
31                 level[e.to]=level[x]+1;
32                 q.push(e.to);
33             }
34         }
35     }
36     return level[tt];
37 }
38 int dfs(int k,int aa){
39     if(k==tt||!aa) return aa;
40     int temp,ans=0;
41     for(int i=0;i<point[k].size();i++){
42         Edge& e=edge[point[k][i]];
43         if(e.cap>e.flow&&level[e.to]==level[k]+1&&(temp=dfs(e.to,min(aa,e.cap-e.flow)))){
44             ans+=temp,aa-=temp;
45             e.flow+=temp,edge[point[k][i]^1].flow-=temp;
46         }
47         if(!aa) return ans;
48     }
49     return ans;
50 }
51 int dinic(){
52     int ans=0;
53     while(bfs()) ans+=dfs(ss,oo);
54     return ans;
55 }
56 int main(){
57 //  freopen("in.txt","r",stdin);
58 //  freopen("out.txt","w",stdout);
59     int ans1=0,ans2=0,ans3=0;
60     scanf("%d",&n);
61     ss=(n<<1)+1,tt=ss+1;
62     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
63     a[n+1]=oo;
64     for(int i=n;i;i--){
65         for(int j=i+1;j<=n+1;j++) if(a[i]<=a[j]) f[i]=max(f[j]+1,f[i]);
66         ans1=max(ans1,f[i]);
67     }
68     printf("%d
",ans1);
69     for(int i=1;i<=n;i++){
70         if(i==1||i==n) spe[++spe[0]]=edge_tot;
71         add_edge(i,i+n,1);
72         if(f[i]==ans1){
73             if(i==1) spe[++spe[0]]=edge_tot;
74             add_edge(ss,i,1);
75         }
76         if(f[i]==1){
77             if(i==n) spe[++spe[0]]=edge_tot;
78             add_edge(i+n,tt,1);
79         }
80     }
81     for(int i=1;i<=n;i++)
82         for(int j=i+1;j<=n;j++) if(a[j]>=a[i]&&f[j]==f[i]-1)
83             add_edge(i+n,j,1);
84     ans2=dinic();
85     printf("%d
",ans2);
86     for(int i=0;i<edge_tot;i++) edge[i].flow=0;
87     for(int i=1;i<=spe[0];i++) edge[spe[i]].cap=oo;
88     ans3=dinic();
89     printf("%d
",ans3);
90     return 0;
91 }