题目描述
«问题描述：
给定正整数序列x1,...,xn 。
（1）计算其最长不下降子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。
«编程任务：
设计有效算法完成（1）（2）（3）提出的计算任务。
输入输出格式
输入格式：
第1 行有1个正整数n，表示给定序列的长度。接下来的1 行有n个正整数n:x1, ..., xn。
输出格式：
第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。
输入输出样例
4
3 6 2 5
2
2
3
说明
n≤500
Solution：
本题简单dp+最大流。
第一问直接煞笔dp。
第二问求最多取出多少个长度为$x=max(f[i])$的子序列，因为每个数要么不选要么只选1次，这样有上下界的题目，考虑拆点跑最大流咯，将每个数拆成$i\rightarrow i'$连流量为1，若$f[i]==1$则$s\rightarrow i$连流量为1，若$f[i]==x$则$i'\rightarrow t$连流量为1，若$f[i]==f[j]+1,j<i,a_j\leq a_i$则$j'\rightarrow i$连流量为1，跑最大流就好了。
第三问可以重复用$a_1$和$a_n$，那么改变的就是与这两点直接相关的边的流量了，我们在第二问的答案基础上，加入新边，$1\rightarrow 1'$流量inf，$n\rightarrow n'$流量inf，$s\rightarrow 1$流量inf，若$f[n]==x$则$n'\rightarrow t$流量inf，再跑下最大流就好了。
（实际上本题第三问有bug，比如最长不下降子序列长度为1，那么第三问答案就应该是inf了，inf不确定，于是乎出锅咯！反正实践证明没这数据，嘿嘿嘿！>.@_@.<）
代码：
/*Code by 520 -- 9.1*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=,M=,inf=0x7fffffff;
int n,a[N],f[N],s,t=;
int h[N],dis[N],to[M],net[M],w[M],cnt=;
int ans1,ans2; il void add(int u,int v,int c){
to[++cnt]=v,net[cnt]=h[u],w[cnt]=c,h[u]=cnt;
to[++cnt]=u,net[cnt]=h[v],w[cnt]=,h[v]=cnt;
} il bool bfs(){
queue<int>q;
memset(dis,-,sizeof(dis));
q.push(s),dis[s]=;
while(!q.empty()){
RE int u=q.front();q.pop();
for(RE int i=h[u];i;i=net[i])
if(dis[to[i]]==-&&w[i]) dis[to[i]]=dis[u]+,q.push(to[i]);
}
return dis[t+]!=-;
} int dfs(int u,int op){
if(u==t+)return op;
int flow=,used=;
for(RE int i=h[u];i;i=net[i]){
int v=to[i];
if(dis[v]==dis[u]+&&w[i]){
used=dfs(v,min(op,w[i]));
if(!used)continue;
flow+=used,op-=used;
w[i]-=used,w[i^]+=used;
if(!op)break;
}
}
if(!flow) dis[u]=-;
return flow;
} il void init(){
scanf("%d",&n);
For(i,,n) scanf("%d",&a[i]),f[i]=;
For(i,,n) For(j,,i-) if(a[i]>=a[j]) f[i]=max(f[i],f[j]+);
For(i,,n) ans1=max(ans1,f[i]);
printf("%d\n",ans1);
For(i,,n) {
add(i,i+n,);
if(f[i]==) add(i+n,t,);
if(f[i]==ans1) add(s,i,);
}
add(t,t+,inf);
For(i,,n) For(j,,i-) if(f[i]==f[j]+&&a[i]>=a[j]) add(i+n,j,);
while(bfs()) ans2+=dfs(s,inf);
printf("%d\n",ans2);
add(n+,t,inf),add(,n+,inf),add(n,n<<,inf);
if(f[n]==ans1) add(s,n,inf);
while(bfs()) ans2+=dfs(s,inf);
printf("%d\n",ans2);
} int main(){
init();
return ;
}