题目传送门
题意
给定一个排列，有两个人轮流操作，第一个人每次可以减少一个逆序对，第二个人每次有 \(50\%\) 的概率减少一个逆序对，也有 \(50\%\) 的概率增加一个逆序对，求让这个序列不含逆序对的最小操作期望。
思路
显然，我们可以列出转移方程：
\[f_i=2+0.5\times f_i+0.5\times f_{i-2}
\]
\(f_i\) 表示含有 \(i\) 个逆序对的最小操作期望。我们把两个人都操作一次设为一组，那么每组操作有 \(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;
}