最長遞增子序列問題

Description

給定正整數序列 x1,x2,x3,...,xn$x_1, x_2, x_3,...,x_n$ （1）計算其最長遞增子序列的長度 s。 （2）計算從給定的序列中最多可取出多少個長度為 s 的遞增子序列。 （3）如果允許在取出的序列中多次使用x1$x_1$和xn$x_n$，則從給定序列中最多可取出多少個長度為 s 的遞增子序列。

Input

第 1 行有 1 個正整數 n，表示給定序列的長度。接下來的 1 行有 n 個正整數x1...xn$x_1...x_n$

Output

第 1 行是最長遞增子序列的長度 s。第 2 行是可取出的長度為 s 的遞增子序列個數。第 3 行是允許在取出的序列中多次使用x1$x_1$和xn$x_n$時可取出的長度為 s 的遞增子序列個數。

題解

題面冠冕堂皇的說著什么最長遞增子序列，數據竟給的是最長不上升子序列的，令人無語。 第一問可以用最簡單的O(n)$O(n)$的動態(tài)規(guī)劃求出，fi$f_i$為以xi$x_i$結束的最長遞增子序列長度，記最長遞增子序列長度為k。 下面考慮建圖，因為每個xi$x_i$只能去一次，那么要限流，所以將每個xi$x_i$拆成兩個點ai$a_i$和bi$b_i$，從ai$a_i$向bi$b_i$連一條容量為1的邊，就可以保證流過xi$x_i$的流量最多為1。 然后從s點向每個fi=1$f_i=1$的ai$a_i$連一條容量為1的邊，然后從每個fi=k$f_i=k$的bi$b_i$向t連一條容量為1的邊。從滿足{i<j,xi<xj,fi+1=fj}$/{i<j,x_i<x_j,f_i+1=f_j/}$的bi$b_i$向aj$a_j$連一條容量為1的邊。這樣，一條從s到t的可行流就是一個最長遞增子序列，最大流即是答案。 對于第三問只需要將<a1,b1>，<an,bn>，<s,a1>$<s,a_1>$，<bn,t>$<b_n,t>$四條邊的容量賦為inf$inf$，再算一遍最大流即可。 【建模分析】 上述建模方法是應用了一種分層圖的思想，把圖每個頂點i按照fi$f_i$的不同分為了若干層，這樣圖中從S出發(fā)到T的任何一條路徑都是一個滿足條件的最長上升子序列。由于序列中每個點要不可重復地取出，需要把每個點拆分成兩個點。單位網絡的最大流就是增廣路的條數，所以最大流量就是第二問結果。第三問特殊地要求x1$x_1$和xn$x_n$可以重復使用，只需取消這兩個點相關邊的流量限制，求網絡最大流即可。