有两个引理
设Fi为以i结尾的最长递增子序列
1.当Fi为1是,i 可能是后面最长递增子序列的起点
2,当Fi取最大值时,同时有多个,那么这多个都是前面最长递增子序列的终点
根据这个性质来网络流....
就没了
建边条件也很好想
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int inf=999999,maxl=0; 5 int n,tot=-1,a[3005],f[3005],h[3005],ans=0,sum=0; 6 struct node{ 7 int from,next,to,rest,full; 8 int last; 9 }e[100005]; 10 void add(int x,int y,int z){ 11 tot++; 12 e[tot].next=h[x]; 13 h[x]=tot; 14 e[tot].from=x; 15 e[tot].to=y; 16 e[tot].rest=z; 17 e[tot].full=z; 18 } 19 20 int dis[3005],g[3005],flow[3005]; 21 bool vis[3005]; 22 23 int bfs(int s,int t){ 24 queue<int>q; 25 dis[s]=0; 26 q.push(s);vis[s]=true; 27 while(!q.empty()){ 28 int u=q.front();vis[u]=false;q.pop(); 29 for(int i=h[u];i!=(-1);i=e[i].next){ 30 if(dis[e[i].to]>dis[u]+1&&g[e[i].to]==(-1)&&e[i].rest>0){ 31 g[e[i].to]=i; 32 flow[e[i].to]=min(flow[u],e[i].rest); 33 dis[e[i].to]=dis[u]+1; 34 if(vis[e[i].to]==false){ 35 vis[e[i].to]=true; 36 q.push(e[i].to); 37 } 38 } 39 } 40 } 41 } 42 43 int EK(int s,int t){ 44 while(1){ 45 memset(vis,false,sizeof(vis)); 46 memset(dis,0x7f,sizeof(dis)); 47 memset(flow,0x7f,sizeof(flow)); 48 memset(g,-1,sizeof(g)); 49 bfs(s,t); 50 if(g[t]==(-1))return 0; 51 ans+=flow[t]; 52 for(int p=t;p!=(s);p=e[g[p]].from){ 53 e[g[p]].rest-=flow[t]; 54 e[g[p]^1].rest+=flow[t]; 55 } 56 57 } 58 } 59 60 int main(){ 61 memset(h,-1,sizeof(h)); 62 cin>>n; 63 for(int i=1;i<=n;i++)cin>>a[i],f[i]=1; 64 for(int i=1;i<=n;i++){ 65 for(int j=1;j<i;j++){ 66 if(a[i]>=a[j])f[i]=max(f[i],f[j]+1); 67 } 68 maxl=max(maxl,f[i]); 69 } 70 for(int i=1;i<=n;i++){ 71 if(f[i]==1){ 72 add(0,i,1); 73 add(i,0,0); 74 } 75 if(f[i]==maxl){ 76 add(i,n+1,1); 77 add(n+1,i,0); 78 } 79 for(int j=1;j<i;j++){ 80 if(a[i]>=a[j]&&f[i]==f[j]+1){ 81 add(j,i,1); 82 add(i,j,0); 83 } 84 } 85 } 86 EK(0,n+1); 87 cout<<maxl<<endl; 88 cout<<ans<<endl;ans=0;if(n==1){cout<<1<<endl;exit(0);} 89 for(int i=0;i<=tot;i++)e[i].rest=e[i].full; 90 for(int i=h[0];i!=(-1);i=e[i].next)if(e[i].to==1)e[i].rest=inf; 91 for(int i=h[n+1];i!=(-1);i=e[i].next)if(e[i].to==n)e[i^1].rest=inf; 92 EK(0,n+1); 93 cout<<ans<<endl; 94 }