POJ-1692: Crossed Matchings

keyword

動的計画法　C

問題概要

長さN,M(<100)の数列a,bが2行横に並んだ状態で与えられる。このとき、a[i]=b[j]であればマッチングとして選べる。ある条件の下で最大マッチングを求める問題。条件とは、

• マッチングに使われた数字が同じである様な辺は交わってはならない(1-1と3-3などは交わっても良いということ)。
• 全ての辺は丁度1本の辺と交わる。

解法

図がないと相当説明しづらい。多分ソースコード読めばやってることは分かってもらえるはず。
配列masは、mas[p][q] = max_{i<=p and j<=q} dp[i][j]　を満たすような配列。
全体の計算量はO(N^3)。

#define MAX_N 102

int dp[MAX_N][MAX_N];
int mas[MAX_N][MAX_N];
int as[MAX_N], bs[MAX_N];
int N, M;

int max(int x, int y){ return x>y?x:y; }

int solve(){
    int i, j, p, q;
    for(i=0; i<N; i++)for(j=0; j<M; j++) dp[i][j] = 0;
    for(i=0; i<N; i++)for(j=0; j<M; j++) mas[i][j] = 0;

    for(i=0; i<N; i++){
        for(j=0; j<M; j++){
            if(as[i]!=bs[j]){
                for(p=i-1;p>=0&&as[p]!=bs[j];p--);
                for(q=j-1;q>=0&&bs[q]!=as[i];q--);
                if(p>=0 && q>=0) dp[i][j] += 2;
                if(p>0 && q>0) dp[i][j] += mas[p-1][q-1];
            }
            if(i>0 && j>0){
                mas[i][j] = max(mas[i-1][j], mas[i][j-1]);
                mas[i][j] = max(mas[i][j], dp[i][j]);
            }
        }
    }

    return mas[N-1][M-1];
}

main(){
    int T, i;
    for(scanf("%d",&T);T--;){
        scanf("%d%d",&N,&M);
        for(i=0;i<N;i++)scanf("%d",as+i);
        for(i=0;i<M;i++)scanf("%d",bs+i);
        printf("%d\n",solve());
    }
}