最长单调递增子序列（网络24题，六）

最长单调递增子序列

由于别的OJ的判题系统的数据太水了。所以，这题我就给出我们OJ的这题链接吧。数据加强了很多！！！

题目链接：Click Here~

算法分析：

是一道最多不相交路径的二分图，要你求出最多的路径。我们可以转换成求解最大流来做。第一次做最多不相交路径的题，卡了好久。好不容易在别的OJ过了，但是在自己OJ卡了半天，调试了好久终于过了^_^。好开心！！！

对于题中的第一问，我们知道这是一个经典的算法，我就不再说了。不懂得自己查阅网上的资料吧，很多的。不过这里我们要用到动态规划的算法来求最长单调递增子序列，因为后面我们的建图将会用的到。由于题目要求每个数只能用一次，所以我们必须拆点。而网上百分之八十的代码都没有，也是因为大家相互抄袭的缘故，所以这题网上的代码基本都不是正解，因为HDU的数据水。所以，可以很轻松的AC。其实，正确的解法我也是学习By_void的网络流24题里知道的，但是他的建图好像错了。不过我的建图精华思想还是学他的。扯太多了，说一下这题的正解吧!

用动态规划求出F[i],表示到第i位时候的最长单调递增序列长度。求出最长的递增序列长度Ans;

1、把序列的每位拆成 和 把 和 之间连一条流为1的边。

2、增加一个supersink and supersource，把F[i]=1的连接到supersource，F[i]=Ans的连接到supersink流为1.

3、对A[i] < A[j] and F[i]+1 = F[j](i

【建模分析】

上述建模方法是应用了一种分层图的思想，把图每个顶点i按照F[i]的不同分为了若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出，需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数，所以最大流量就是第二问结果。第三问特殊地要求x1和xn可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 1000+10; const int INF = ~0U >> 1; struct Edge{ int from,to,cap,flow; Edge(){} Edge(int _fr,int _t,int _c,int _f) :from(_fr),to(_t),cap(_c),flow(_f){} }; vector
       
         edges; vector
        
          G[maxn]; int S,T,N,Ans,F[maxn],A[maxn]; int d[maxn],cur[maxn]; bool vst[maxn]; void LIS() { for(int i = 1;i <= N;++i){ F[i] = 1; for(int j = 1;j < i;++j) if(A[i] > A[j]&&F[i]
         
           Ans) Ans = F[i]; } } void Init() { for(int i = 0;i < maxn;++i) G[i].clear(); edges.clear(); Ans = 1; S = 0,T = N+N+1; for(int i = 1;i <= N;++i) scanf("%d",&A[i]); } inline void AddEdge(int from,int to,int cap) { edges.push_back((Edge){from,to,cap,0}); edges.push_back((Edge){to,from,0,0,}); int sz = edges.size(); G[from].push_back(sz-2); G[to].push_back(sz-1); } inline void Build() { for(int i = 1;i <= N;++i){ AddEdge(i,i+N,1); if(F[i]==1) AddEdge(S,i,1); else //注意这里！！！ if(F[i]==Ans) AddEdge(i+N,T,1); for(int j = 1;j < i;++j) if(A[i]>A[j]&&F[j]+1==F[i]) AddEdge(j+N,i,1); } } bool BFS() { memset(vst,false,sizeof(vst)); queue
          
            Q; Q.push(S); d[S] = 0; vst[S] = true; while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = 0;i < (int)G[u].size();++i){ Edge& e = edges[G[u][i]]; if(!vst[e.to]&&e.cap > e.flow){ vst[e.to] = true; d[e.to] = d[u]+1; Q.push(e.to); } } } return vst[T]; } int DFS(int u,int a) { if(u==T||a==0) return a; int f,flow = 0; for(int& i = cur[u];i < (int)G[u].size();++i){ Edge& e = edges[G[u][i]]; if(d[e.to]==d[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){ e.flow += f; edges[G[u][i]^1].flow -= f; flow += f; a -= f; if(a==0)break; } } return flow; } int Maxflow() { int flow = 0; while(BFS()){ memset(cur,0,sizeof(cur)); flow += DFS(S,INF); } return flow; } void Solve() { LIS(); printf("%d\n",Ans); if(Ans==1){ //注意这里！！跟前面的else有关(当Ans=1时) printf("%d\n",N); return; } Build(); int flow = Maxflow(); printf("%d\n",flow); } int main() { while(~scanf("%d",&N)){ Init(); Solve(); } return 0; } 
          
         
        
       
      
     
    
   
  

加强的数据：

Input

4

1 1 2 2

5

5 4 3 2 1

4

3 6 2 5

5

1 1 2 3 3

Output(长度为Ans的个数)

2

5

2

1

最长递增子序列问题

问题描述: 给定正整数序列x1,...,xn 。

(1)计算其最长递增子序列的长度 s。

(2)计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。

(3)如果允许在取出的序列中多次使用 x1 和 xn,则从给定序列中最多可取出多少个长度为 s 的递增子序列。

编程任务: 设计有效算法完成(1)(2)(3)提出的计算任务。

数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 1 个正整数 n,表示给定序列的长度。接 下来的 1 行有 n 个正整数 x1 ,.., xn 。

结果输出: 程序运行结束时,将任务(1)(2)(3)的解答输出到文件 output.txt 中。

第 1 行是最长 递增子序列的长度 s。

第 2 行是可取出的长度为 s 的递增子序列个数。

第 3 行是允许在取出 的序列中多次使用 x1 和 xn 时可取出的长度为 s 的递增子序列个数。

输入文件示例 input.txt 4 3 6 2 5

输出文件示例 output.txt 2 2 3