# CFR 790 C. Bear and Company ( DP )

Problem - C - Codeforces

The first line of the input contains an integer n (1 ≤ n ≤ 75) — the length of the string.
The second line contains a string s, consisting of uppercase English letters. The length of the string is equal to n.
TL: 1000 ms
ML: 256 MB

dp[ i ][ j ][ k ][ l ] : 已使用 i 個 'V' 字符，j 個 'K' 字符，k 個其它的字符，結尾是否為 'V'，到達此狀態的最小總花費。

O( N^3 lg N ) / O( N^3 )

```#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
if( x <= v ) return 0;
x = v; return 1;
}

const int MAXN = 75;

int N;
string seq;
int dp[ MAXN + 1 ][ MAXN + 1 ][ MAXN + 1 ][ 2 ];
vector< int > pos[ 256 ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
cin >> seq;
for( int i = 0; i < N; ++i ){
if( seq[ i ] != 'V' and seq[ i ] != 'K' ){
seq[ i ] = '#';
}
pos[ seq[ i ] ].emplace_back( i );
}
memset( dp, 0x3f3f3f3f, sizeof( dp ) );
dp[ 0 ][ 0 ][ 0 ][ 0 ] = 0;
for( int i = 0; i <= pos[ 'V' ].size(); ++i ){
for( int j = 0; j <= pos[ 'K' ].size(); ++j ){
for( int k = 0; k <= pos[ '#' ].size(); ++k ){
for( int l = 0; l < 2; ++l ){
auto cost = [ & ]( int x ){
int a = lower_bound( pos[ 'V' ].begin(), pos[ 'V' ].end(), x ) - pos[ 'V' ].begin();
int b = lower_bound( pos[ 'K' ].begin(), pos[ 'K' ].end(), x ) - pos[ 'K' ].begin();
int c = lower_bound( pos[ '#' ].begin(), pos[ '#' ].end(), x ) - pos[ '#' ].begin();
return max( 0, a - i ) + max( 0, b - j ) + max( 0, c - k );
};
if( i + 1 <= pos[ 'V' ].size() ){
upmin( dp[ i + 1 ][ j ][ k ][ 1 ], dp[ i ][ j ][ k ][ l ] + cost( pos[ 'V' ][ i ] ) );
}
if( not l and j + 1 <= pos[ 'K' ].size() ){
upmin( dp[ i ][ j + 1 ][ k ][ 0 ], dp[ i ][ j ][ k ][ l ] + cost( pos[ 'K' ][ j ] ) );
}
if( k + 1 <= pos[ '#' ].size() ){
upmin( dp[ i ][ j ][ k + 1 ][ 0 ], dp[ i ][ j ][ k ][ l ] + cost( pos[ '#' ][ k ] ) );
}
}
}
}
}
cout << min( dp[ pos[ 'V' ].size() ][ pos[ 'K' ].size() ][ pos[ '#' ].size() ][ 0 ],
dp[ pos[ 'V' ].size() ][ pos[ 'K' ].size() ][ pos[ '#' ].size() ][ 1 ] ) << endl;
return 0;
}
```