本文正體字版由OpenCC轉換

【問題分析】

第一問時LIS，動態規劃求解，第二問和第三問用網絡最大流解決。

【建模方法】

首先動態規劃求出F[i]，表示以第i位爲開頭的最長上升序列的長度，求出最長上升序列長度K。

1、把序列每位i拆成兩個點<i.a>和<i.b>，從<i.a>到<i.b>連接一條容量爲1的有向邊。 2、建立附加源S和匯T，如果序列第i位有F[i]=K，從S到<i.a>連接一條容量爲1的有向邊。 3、如果F[i]=1，從<i.b>到T連接一條容量爲1的有向邊。 4、如果j>i且A[i] < A[j]且F[j]+1=F[i]，從<i.b>到<j.a>連接一條容量爲1的有向邊。

求網絡最大流，就是第二問的結果。把邊(<1.a>,<1.b>)(<N.a>,<N.b>)(S,<1.a>)(<N.b>,T)這四條邊的容量修改爲無窮大，再求一次網絡最大流，就是第三問結果。

【建模分析】

上述建模方法是應用了一種分層圖的思想，把圖每個頂點i按照F[i]的不同分爲了若干層，這樣圖中從S出發到T的任何一條路徑都是一個滿足條件的最長上升子序列。由於序列中每個點要不可重複地取出，需要把每個點拆分成兩個點。單位網絡的最大流就是增廣路的條數，所以最大流量就是第二問結果。第三問特殊地要求x1和xn可以重複使用，只需取消這兩個點相關邊的流量限制，求網絡最大流即可。

最長遞增子序列問題
問題描述: 給定正整數序列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

上次修改時間 2017-02-03