题解：CF351B Jeff and Furik

· · 题解

题目传送门

题意

给定一个排列，有两个人轮流操作，第一个人每次可以减少一个逆序对，第二个人每次有 50\% 的概率减少一个逆序对，也有 50\% 的概率增加一个逆序对，求让这个序列不含逆序对的最小操作期望。

思路

显然，我们可以列出转移方程：

f_i=2+0.5\times f_i+0.5\times f_{i-2} 最后我们可以用 $O(n^2)$ 的复杂度求出有多少逆序对，再 $O(1)$ 计算即可。设 $ans$ 为逆序对数，如果 $ans$ 是偶数，那么答案即为 $ans\times 2$，如果是奇数，那么就是 $ans\div 2\times 4+1

注意边界条件，f_0=0，f_1=1 因为只有一个逆序对时，第一个人可以直接更改，所以只操作一次。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
ll n,a[N],ans,dp[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i]>a[j])ans++;
    cout<<(ans&1)+(ans)/2*4;
    return 0;
}