[CodeVS 2185] 最長公共上升子序列：DP

題意：求兩個序列的最長公共嚴格上升子序列的長度。

NOI 題庫裡有這道題，序列長度<=500。容易想到一個 O(n3) 的做法：設

f[i][j]

為a[0..i]、b[0..j]以i、j結尾的最長公共嚴格上升子序列的長度，同時維護

g[i][j] = max { f[k][j] [k<=i & a[k]=b[j]] } + 1

。實作中，我把

g

滾動了，于是需要逆序枚舉。由于NOI題庫沒有Special Judge，交到了CodeVS。作為 O(n3) 的算法當然可以被卡，不過神奇地通過了所有測試資料。

網上有更好的做法。首先，

f

數組完全可以不要。

g[i][j] = max { g[i-1][k] [k<j & b[k]<b[j]] } + 1 (a[i]=b[j]), g[i-1][j] (a[i]!=b[j])

。外層枚舉

i

，内層枚舉

j

，發現條件中的

b[k]<b[j]

變為

b[k]<一個常量

，從左到右維護滿足該條件的

max { g[i-1][k] }

即可。

記錄字典序最小的方案可以用

vector

：http://stone906229046.blog.163.com/blog/static/267075001201610781331357/

O(n3)

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_M = ;
int a[MAX_M], b[MAX_M], f[MAX_M][MAX_M], g[MAX_M];

int main()
{
    int m, n;
    scanf("%d", &m);
    for (int i = ; i < m; ++i)
        scanf("%d", &a[i]);
//  scanf("%d", &n);
    n = m;
    for (int i = ; i < n; ++i)
        scanf("%d", &b[i]);
    int ans = ;
    for (int j = ; j < n; ++j)
        if (a[] == b[j])
            f[][j] = g[j] = ;
    for (int i = ; i < m; ++i) {
        for (int j = n-; j >= ; --j) {
            if (a[i] != b[j])
                continue;
            f[i][j] = ;
            for (int k = ; k < j; ++k)
                if (b[k] < b[j])
                    f[i][j] = max(f[i][j], g[k]+);
            g[j] = max(g[j], f[i][j]);
            ans = max(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
    return ;
}
           

O(n2)

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_M = ;
int a[MAX_M], b[MAX_M], g[MAX_M];

int main()
{
    int m, n;
    scanf("%d", &m);
    for (int i = ; i < m; ++i)
        scanf("%d", &a[i]);
    n = m;
    for (int i = ; i < n; ++i)
        scanf("%d", &b[i]);

    int ans = ;

    for (int i = ; i < m; ++i) {
        int v = ; // v = g[k], k<j & b[k]<b[j]=a[i]
        for (int j = ; j < n; ++j) {
            if (b[j] < a[i])
                v = max(v, g[j]);
            else if (b[j] == a[i]) {
                g[j] = max(g[j], v+);
                ans = max(ans, g[j]);
            }
        }
    }

    printf("%d\n", ans);
    return ;
}