- 给定一个长度为(n)的序列，求：
- 这个序列最长不下降子序列长度(s)。
- 在每个元素只能使用一次时最多能取出多少个长度为(s)的不下降子序列。
- 在只有第(1)个和第(n)个元素能无限次使用（其他元素依然只能使用一次）时最多能取出多少个不同的长度为(s)的不下降序列。
- (nle500)
最长不下降子序列
首先，我们可以通过非常简单的(DP)求出以第(i)个位置为结尾的最长不下降子序列长度(f_i)，这样就能轻松解决第一问。
一个显然的结论，在任何最长不下降子序列中，(a_i)都必然是作为第(f_i)个元素出现的。
所以我们可以考虑按(f_i)分层建图，只在相邻两层之间满足(i<j)的前一层的(a_i)小于等于后一层的(a_j)时，我们才从(i)向(j)连一条边。
然后针对每个点只能选一次的限制，我们只要把所有点都拆成两个点，在其中连一条容量为(1)的边即可解决第二问。
最后考虑第三问，由于(a_1)和(a_n)分别只可能作为最长上升子序列的第一个元素和最后一个元素，所以我们只要把和它们有关的所有边容量修改为(INF)即可。
具体实现中，我们不必真的去修改容量重跑网络流，只要再对所有和(a_1,a_n)有关的边重新建一条容量为(INF)的边，并在原图的基础上接着跑网络流即可。
代码：(O(Dinic))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500
#define INF (int)1e9
using namespace std;
int n,a[N+5],f[N+5];
class NetFlow
{
private:
#define PS (2*N+2)
#define ES (N*N)
#define s (2*n+1)
#define t (2*n+2)
#define P(i,j) (((i)-1)*n+(j))
#define add(x,y,f) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].F=f)
int ee,lnk[PS+5],cur[PS+5],d[PS+5],q[PS+5];struct edge {int F,to,nxt;}e[2*ES+5];
I bool BFS()
{
RI i,k,H=1,T=1;for(i=1;i<=t;++i) d[i]=0;d[q[1]=s]=1;W(H<=T&&!d[t])
for(i=lnk[k=q[H++]];i;i=e[i].nxt) e[i].F&&!d[e[i].to]&&(d[q[++T]=e[i].to]=d[k]+1);
return d[t]&&memcpy(cur,lnk,sizeof(lnk)),d[t];
}
I int DFS(CI x=s,RI f=1e9)
{
if(!f||x==t) return f;RI i,g,res=0;for(i=cur[x];i;i=e[i].nxt)
{
if(d[e[i].to]^(d[x]+1)||!(g=DFS(e[i].to,min(f,e[i].F)))) continue;
if(e[i].F-=g,e[((i-1)^1)+1].F+=g,res+=g,!(f-=g)) break;
}return cur[x]=i,res;
}
public:
I void Add(CI x,CI y,CI f) {add(x,y,f),add(y,x,0);}
I int MaxFlow() {RI f=0;W(BFS()) f+=DFS();return f;}
}D;
int main()
{
RI i,j,g,Mx=0;if(scanf("%d",&n),n==1) return puts("1
1
1"),0;//特判n=1
for(i=1;i<=n;Mx=max(Mx,f[i++])) for(scanf("%d",a+i),
f[i]=1,j=1;j^i;++j) a[j]<=a[i]&&(f[i]=max(f[i],f[j]+1));//动态规划求最长不下降子序列
for(printf("%d
",Mx),i=1;i<=n;++i)
{
D.Add(i,n+i,1),f[i]==1&&(D.Add(s,i,1),0),f[i]==Mx&&(D.Add(n+i,t,1),0);//和超级源超级汇之间的连边
for(j=i+1;j<=n;++j) a[i]<=a[j]&&f[i]+1==f[j]&&(D.Add(n+i,j,1),0);//分层建图
}
for(printf("%d
",g=D.MaxFlow()),i=2;i^n;++i)//和a[1],a[n]有关的边
a[1]<=a[i]&&f[i]==2&&(D.Add(n+1,i,INF),0),a[i]<=a[n]&&f[i]==f[n]-1&&(D.Add(n+i,n,INF),0);//两层之间的边
D.Add(s,1,INF),D.Add(1,n+1,INF),D.Add(n,n+n,INF),f[n]==Mx&&(D.Add(n+n,t,INF),0);//与超级源汇之间的边以及拆得两点间的边
return printf("%d
",g+D.MaxFlow()),0;//在原图基础上接着跑
}