CFR 132 C. Logo Turtle ( DP )

Problem - C - Codeforces

題意：
給一個操作序列，若字符為 'T' 則轉向，原地不動，若為 'F' 則向原方向前方走一格。求更改恰好 N 次字符後，最遠可以走多遠。一個字符可以修改多次。

資料規模：
The first line of input contains a string commands — the original list of commands. The string commands contains between 1 and 100 characters, inclusive, and contains only characters "T" and "F".
The second line contains an integer n (1 ≤ n ≤ 50) — the number of commands you have to change in the list.
TL: 2000 ms
ML: 256 MB

解法：
dp[ i ][ j ][ k ]：已考慮前 i 個字符，已修改 j 次，目前方向為右
轉移時直接枚舉當前的字符要修改幾次。

時間 / 空間複雜度：
O( | str | * N^2 ) / O( | str | * N )

string seq;
int N;

void init(){
  cin >> seq;
  cin >> N;
}

vvvi dp;
int ans;

void preprocess(){
  dp = vvvi( seq.size() + 1, vvi( N + 1, vi( 2, -INF ) ) );
  dp[ 0 ][ 0 ][ 0 ] = 0;
  for( int i = 0; i < seq.size(); ++i ){
    for( int j = 0; j <= N; ++j ){
      for( int k = 0; k < 2; ++k ){
        for( int l = 0; l + j <= N; ++l ){
          int turn = k ^ seq[ i ] == 'T' ^ l & 1;
          if( turn != k ){
            upmax( dp[ i + 1 ][ l + j ][ turn ], dp[ i ][ j ][ k ] );
          } else{
            upmax( dp[ i + 1 ][ l + j ][ turn ], dp[ i ][ j ][ k ] + ( turn ? -1 : 1 ) );
          }
        }
      }
    }
  }
  upmax( ans, max( dp[ seq.size() ][ N ][ 0 ], dp[ seq.size() ][ N ][ 1 ] ) );
  dp = vvvi( seq.size() + 1, vvi( N + 1, vi( 2, INF ) ) );
  dp[ 0 ][ 0 ][ 0 ] = 0;
  for( int i = 0; i < seq.size(); ++i ){
    for( int j = 0; j <= N; ++j ){
      for( int k = 0; k < 2; ++k ){
        for( int l = 0; l + j <= N; ++l ){
          int turn = k ^ seq[ i ] == 'T' ^ l & 1;
          if( turn != k ){
            upmin( dp[ i + 1 ][ l + j ][ turn ], dp[ i ][ j ][ k ] );
          } else{
            upmin( dp[ i + 1 ][ l + j ][ turn ], dp[ i ][ j ][ k ] + ( turn ? -1 : 1 ) );
          }
        }
      }
    }
  }
  upmax( ans, max( -dp[ seq.size() ][ N ][ 0 ], -dp[ seq.size() ][ N ][ 1 ] ) );
}

void solve(){
  cout << ans << endl;
}