(codeforces) 463D. Gargari and Permutations

http://codeforces.com/contest/463/problem/D


這題的大意是求五條陣列的LCS，長度1000，數值1~1000

一般的LCS求法是 :
if (n[i] == n[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i][j-1] , dp[i-1][j]) ;

那，我們其實可以換個圖論的想法

如果a-->b有可能是LCS的部分，那我們就建個邊

那，在經過k條陣列，如果a-->b總共有k條，那可能是總LCS的一部分

例如：陣列是4,2,1,3，那我們就建(4-->2,4-->1,4-->3,2-->1,2-->3,1-->3)

之後，我們就得到一個DAG，目標就變成求DAG的最長路徑，就很簡單了XDDD

複雜度：O(n^2)

http://codeforces.com/contest/463/submission/17311738