CFR 790 C. Bear and Company ( DP )

題意：
給一個長度為 N 的大寫英文字母組成的字串，一次操作可以將任一兩相鄰字符交換，問最少要多少次交換才能使得 "VK" 不以子字串形式出現。

資料規模：
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

解法：
注意到只能交換相鄰字符。
一般有看起來比較特殊的限制條件，可以先想想看有無該條件會有何影響。
如果可以任意交換相異位置的字符，會變成要維護類似群的集合。
但如果只能交換相鄰元素，最少交換次數可能就跟逆序數對比較有關係。
因為只有三種字符 { 'V', 'K', 其它 }，而考慮操作完成後的字串 F，可以想到如果 F[ 0 ] 要用其中一個字符，那一定來自原字串裡該字符最靠前的。對於 F 的所有元素都是如此，總是從原字串取得對應的字符中還沒被使用的最前的位置。這提示我們，只要確定已經對三種字符分別取了幾個，轉移也會唯一確定。考慮定義動態規劃：
dp[ i ][ j ][ k ][ l ] : 已使用 i 個 'V' 字符，j 個 'K' 字符，k 個其它的字符，結尾是否為 'V'，到達此狀態的最小總花費。
可以發現，轉移時如果要加入某個字符，首先可以很簡單地查到它在原字串中第一個未被使用的位置，令之 x。
加入的花費是原字串中在 x 之前，還沒被使用的字符數量總和，因為這些字符一定會跑到後面，所以和當前這個字符的交換是不可避免的，而其它字符則完全無關。

時間 / 空間複雜度：
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;
}