乍一看好像是个DP，做着做着发现锅了……
好吧，试试WLL。
首先用dp求出最长不下降子序列的长度（简单不再赘述）
问题2：
超级源点与所有f[i]=0的点的入口相连，边权为1。
超级汇点与所有f[i]=ans的点的出口相连，边权为inf。
连所有的边满足i<j，a[i]<=a[j]，f[i]=f[j]-1，边权为inf。
连每个点的入口和出口，边权为1.
（这简直是套路……）
问题3：
将1和n的出入口边权改为inf，将超级源点到1的边权改为inf
几个小细节：
1.ans=1时输出：1,n,n
2.重建图时边数清零，beg赋值为-1
搞定，看代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e4; const int maxm=1e5; int n,a[maxn],f[maxn]; int beg[maxn],nex[maxm],to[maxm],w[maxm],e; inline void add(int x,int y,int z){ nex[e]=beg[x];beg[x]=e; to[e]=y;w[e]=z;e++; } int dep[maxn]; queue<int>q; inline int bfs(){ memset(dep,0x3f,sizeof(dep)); while(!q.empty())q.pop(); q.push(0); dep[0]=0; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=beg[x];~i;i=nex[i]){ int t=to[i]; if(w[i]&&dep[t]>3*n){ dep[t]=dep[x]+1; q.push(t); } } } return dep[2*n+1]<3*n; } inline int dfs(int x,int lim){ if(x==2*n+1||!lim)return lim; int ans=0; for(int i=beg[x];~i;i=nex[i]){ int t=to[i]; if(dep[t]==dep[x]+1){ int flow=dfs(t,min(lim,w[i])); ans+=flow; lim-=flow; w[i]-=flow; w[i^1]+=flow; } } return ans; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ f[i]=1; for(int j=1;j<i;j++) if(a[i]>=a[j])f[i]=max(f[i],f[j]+1); } int ans=0,tot=0,res=0; for(int i=1;i<=n;i++) ans=max(ans,f[i]); if(ans==1){ printf("1 %d %d ",n,n); return 0; } printf("%d ",ans); memset(beg,-1,sizeof(beg)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[j]>=a[i]&&f[j]-f[i]==1){ add(i+n,j,1e9); add(j,i+n,0); } for(int i=1;i<=n;i++) add(i,i+n,1),add(i+n,i,0); for(int i=1;i<=n;i++) if(f[i]==1)add(0,i,1e9),add(i,0,0); for(int i=1;i<=n;i++) if(f[i]==ans)add(i+n,2*n+1,1e9),add(2*n+1,i+n,0); while(bfs())tot+=dfs(0,1e9); printf("%d ",tot); e=0; memset(beg,-1,sizeof(beg)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[j]>=a[i]&&f[j]-f[i]==1){ if(i==1&&j==n){ add(i+n,j,1); add(j,i+n,0); }else{ add(i+n,j,1e9); add(j,i+n,0); } } add(1,n+1,1e9),add(n+1,1,0); add(n,2*n,1e9),add(2*n,n,0); for(int i=2;i<n;i++) add(i,i+n,1),add(i+n,i,0); add(0,1,1e9),add(1,0,0); for(int i=2;i<n;i++) if(f[i]==1)add(0,i,1),add(i,0,0); for(int i=1;i<=n;i++) if(f[i]==ans)add(i+n,2*n+1,1e9),add(2*n+1,i+n,0); while(bfs())res+=dfs(0,1e9); printf("%d ",res); return 0; }
深深地感到自己的弱小。