CFR 132 C. Logo Turtle ( DP )

Problem - C - Codeforces

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