0w1

CFR 607 B. Zuma ( DP )

Problem - 607B - Codeforces
非常神奇的一道題
題意:
給一個數列,每一次操作將一連續區間的回文刪除,刪除某區間後其左右會連接。求最少刪除數,使整個數列被刪除。
解法:
dp[ i ][ j ] : 刪除原序列的 [ i, j ] 區間元素需要的最少操作數。
dp[ i ][ j ] =
min{
dp[ i + 1 ][ j ] + 1,
dp[ i + 2 ][ j ], if C[ i ] == C[ i + 1 ]
dp[ i + 1 ][ k - 1 ] + dp[ k + 1 ][ j ], if C[ i ] == C[ k ]
}
最後一個轉移式想一想就會懂。但我還真不知道這要怎麼在比賽中想出來,誰有什麼想法的話,務必告訴我,感謝。

int N;
vi C;

void init(){
    cin >> N;
    C = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> C[ i ];
}

vvi dp;

int dfs( int lb, int rb ){ // [ lb, rb ]
    if( lb > rb )
        return 0; 
    int &ans = dp[ lb ][ rb ];
    if( ~ans )
        return ans;
    ans = 1 + dfs( lb + 1, rb );
    if( C[ lb ] == C[ lb + 1 ] )
        upmin( ans, 1 + dfs( lb + 2, rb ) );
    for( int i = lb + 2; i <= rb; ++i )
        if( C[ lb ] == C[ i ] )
            upmin( ans, dfs( lb + 1, i - 1 ) + dfs( i + 1, rb ) );
    return ans;
}

void preprocess(){
    dp = vvi( N, vi( N, -1 ) );
    for( int i = 0; i < N; ++i )
        dp[ i ][ i ] = 1;
}

void solve(){
    cout << dfs( 0, N - 1 ) << endl;
}