p1692.cpp

来自「大概POJ上50道比较难的题的代码」· C++ 代码 · 共 41 行

#include <iostream>
using namespace std;
const int MAXN = 110;
int main(){
    int N;
    cin >> N;
    while(N--){
        int a[MAXN],b[MAXN];
        int pos1[MAXN][MAXN],pos2[MAXN][MAXN],f[MAXN][MAXN];
        int n1,n2;
        memset(f,0,sizeof(f));
        cin >> n1 >> n2;
        for(int i = 1;i <= n1;++i) cin >> a[i];
        for(int i = 1;i <= n2;++i) cin >> b[i];
        memset(pos1,0,sizeof(pos1));
        memset(pos2,0,sizeof(pos2));
        for(int i = 1;i <= n2;++i)
            for(int j = 1;j <= n1;++j)
                for(int k = j;k > 0;--k)
                    if(b[i] == a[k]){
                        pos1[i][j] = k;
                        break;
                    }
        for(int i = 1;i <= n1;++i)
            for(int j = 1;j <= n2;++j)
                for(int k = j;k > 0;--k)
                    if(a[i] == b[k]){
                        pos2[i][j] = k;
                        break;
                    }
        for(int i = 2;i <= n1;++i)
            for(int j = 2;j <= n2;++j){
                f[i][j] = max(f[i-1][j],f[i][j-1]);
                if(a[i] != b[j] && pos1[j][i] && pos2[i][j]){
                    f[i][j] = max(f[i][j],f[pos1[j][i]-1][pos2[i][j]-1] + 2);
                }
            }
        cout << f[n1][n2] << endl;
    }
}