UVA 1625 Color Length ( DP 維護未來花費 )

UVa Online Judge
由於花費的定義是每個顏色的最後出現位置減去最先出現位置的總和，樸素的動態規劃做法是不好做的。比較好的方法是根據當前的字母是否為最後一個，或是剛開始，維護由這個狀態轉移到別的狀態所需要的花費。令 dp( i, j ) 為已經使用 p的前 i個字母和 q的前 j個字母的情況下的最少花費，c( i, j ) 為由當前這個狀態轉移( 新增任何一種字母 )到任一個新的狀態所需要增加的花費，那麼
dp( i, j ) = min{ dp( i - 1, j ) + c( i - 1, j ), dp( i, j - 1 ) + c( i, j - 1 ) }
c陣列的具體維護方法大致上是若且唯若當前加入的這個字母是第一個的字母，那麼將來新增任何一個字母都要因為它增加一個花費，但若且唯若當前加入的這個字母是最後的字母，要將它從這個花費陣列裡刪去。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
const int MAXN = 5e3 + 5;

char p[MAXN], q[MAXN];
int sp[26], sq[26], ep[26], eq[26];
int d[MAXN][MAXN], c[MAXN][MAXN];

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%s%s", p + 1, q + 1);
        int n = strlen( p + 1 ), m = strlen( q + 1 );
        for(int i = 1; i <= n; ++i) p[i] -= 'A';
        for(int i = 1; i <= m; ++i) q[i] -= 'A';
        for(int i = 0; i < 26; ++i){
            sp[i] = sq[i] = INF;
            ep[i] = eq[i] = 0;
        }
        for(int i = 1; i <= n; ++i){
            sp[ p[i] ] = min( sp[ p[i] ], i );
            ep[ p[i] ] = i;
        }
        for(int i = 1; i <= m; ++i){
            sq[ q[i] ] = min( sq[ q[i] ], i );
            eq[ q[i] ] = i;
        }

        for(int i = 0; i <= n; ++i)
            for(int j = 0; j <= m; ++j){
                if( !i && !j ) continue;

                int v1 = INF, v2 = INF;
                if( i > 0 ) v1 = d[i - 1][j] + c[i - 1][j];
                if( j > 0 ) v2 = d[i][j - 1] + c[i][j - 1];
                d[i][j] = min( v1, v2 );

                if( i > 0 ){
                    c[i][j] = c[i - 1][j];
                    if( sp[ p[i] ] == i && sq[ p[i] ] > j ) ++c[i][j];
                    if( ep[ p[i] ] == i && eq[ p[i] ] <= j ) --c[i][j];
                } else{
                    c[i][j] = c[i][j - 1];
                    if( sq[ q[j] ] == j && sp[ q[j] ] > i ) ++c[i][j];
                    if( eq[ q[j] ] == j && ep[ q[j] ] <= i ) --c[i][j];
                }
            }

        printf("%d\n", d[n][m]);
    }
    return 0;
}