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; }