HDU 1423 - Greatest Common Increasing Subsequence

Problem : Given two sequence, find the longest common subsequence s.t. the chosen subsequence should also increasing.
Solution :
1) The problem can be transformed to NxM grid, grid[i][j] has number if a[i]==b[j]. Any common increasing subsequence in original problem, is a list of chosen numbers in grid s.t. if the chosen number is sorted in row, the column id is increasing as well as its value. Thus the problem is transformed to find the most number of row-column-value-increasing sequence in such form.

2) Denote f[i][j][k] to be in sub-grid grid[1..i][1..j] the smallest tail number in length-k sequence. Then f[i][j]=getmin(f[i-1][j], f[i][j-1]) if a[i]!=b[j]. Otherwise, f[i][j][k]=[(1) if (f[i-1][j-1][k]>=a[i] and f[i-1][j-1][k-1]<a[i]) then a[i]. (2) Otherwise f[i-1][j-1][k]].

3) The solution in above is O(NM^2), since sequence copy need O(M). However, this problem is special. For f[i][j], the i-th row's number should always a[i], the j-th column's number should always b[j]. Thus the only difference with f[i-1][j] and f[i][j] is the sequence ended with a[i]. If a[i]!=b[j], find longest sequence ended at i-th row and before j-th column, assume it is k, then update f[i-1][j][k] (For other f[i][j][k'], f[i-1][j][k'] should also has). If a[i]=b[j], then j-th row should always be a[i]. So it does not make difference to update f[i-1][j] or f[i-1][j] with a[i] to get f[i][j]. Since if a[i] can update f[i-1][j-1] but not f[i-1][j], then f[i-1][j] also uses a[i] to change f[i-1][j-1]'s same element.