CFR 351 B. Jeff and Furik ( DP, Expectation )

Problem - 351B - Codeforces

題意：
給你一個 1 ~ N 的排列。現在兩個人輪流操作，第一個人會選擇兩個數字，且一定選左數比右數大的兩個數字，並進行交換。第二個人會以 0.5 的機率選左數比右數大的兩個數字。求達到第一次排好期望需要幾次操作。

資料規模：
1 ≤ n ≤ 3000
TL: 1000 ms
ML: 256 MB

解法：
因為是選擇相鄰的兩個數字，第一個人會將操作前的逆序數對數少一，而第二個人會以 0.5 的機率將操作前的逆序對數少一，另外 0.5 的機率使之多一。當逆序數對數為 0 的時候，剩餘期望操作數為 0。考慮動態規劃：
dp[ i ]：當剩餘逆序對數為 i 的時候，剩餘期望操作數。
為求方便，先試試看能不能將兩個人的操作綁在一起算。
dp[ i ] = 1 + 1 + 0.5 * dp[ i - 1 - 1 ] + 0.5 * dp[ i - 1 + 1 ]
________= 4 + dp[ i - 2 ]
便發現，只要 i 不是 1 就不會有什麼問題，而 dp[ 1 ] 顯然為 1。

時間 / 空間複雜度：
O( N )

int N;
vi P;

void init(){
  cin >> N;
  P = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> P[ i ];
  }
}

int inv_cnt;
vi dp;

void preprocess(){
  for( int i = 0; i < N; ++i ){
    for( int j = i + 1; j < N; ++j ){
      inv_cnt += P[ i ] > P[ j ];
    }
  }
  dp = vi( inv_cnt + 1 );
  dp[ 1 ] = 1;
  for( int i = 0; i + 2 <= inv_cnt; ++i ){
    dp[ i + 2 ] = dp[ i ] + 4;
  }
}

void solve(){
  cout << dp[ inv_cnt ] << endl;
}