程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces 513G1 513G2 Inversions problem 概率dp

Codeforces 513G1 513G2 Inversions problem 概率dp

編輯：關於C++

題目鏈接：點擊打開鏈接

題意:

給定n ，k

下面n個數表示有一個n的排列，

每次操作等概率翻轉一個區間，操作k次。

問：

k次操作後逆序數對個數的期望。

思路：

dp[i][j]表示 a[i] 在a[j] j前面的概率

初始就是 dp[i][j] = 1( i < j )

則對於翻轉區間 [i, j], 出現的概率 P = 1 / ( n * (n+1) /2)

並且會導致 [i, j]內元素位置交換，枚舉這次翻轉的區間時所有的轉移情況

#include   
#include   
#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template 
inline void pt(T x) {
	if (x <0) {
		putchar('-');
		x = -x;
	}
	if (x>9) pt(x / 10);
	putchar(x % 10 + '0');
}
using namespace std;
typedef long long ll;
const int N = 105;
int n, m, a[N];
double dp[N][N], tmp[N][N];
int main(){
	while (cin >> n >> m){
		for (int i = 1; i <= n; i++)rd(a[i]);
		memset(dp, 0, sizeof dp);
		for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++)dp[i][j] = 1;
		double P = 1.0 / ( n * (n + 1) / 2.0 );
		while (m--){
			memcpy(tmp, dp, sizeof dp);
			memset(dp, 0, sizeof dp);
			for (int x = 1; x <= n; x++)
			for (int y = x; y <= n; y++)
			{
				for (int i = 1; i <= n; i++)
				for (int j = i + 1; j <= n; j++){
					int a = i, b = j; //(i,j)在區間[x,y]對換後所對應的點為(a,b)
					if (x <= a && a <= y) a = x + y - a;
					if (x <= b && b <= y) b = x + y - b;
					//當且僅當區間[x, y]包含(i,j)時i>j變成j>i(而現在對應的位置是a,b)，否則是不變的
					if (a > b)swap(a, b);
					if (x <= i && j <= y)
						dp[a][b] += (1 - tmp[i][j])*P;
					else
						dp[a][b] += tmp[i][j] * P;
				}
			}
						
		}
		double ans = 0;
		for (int i = 1; i <= n; i++)
			for (int j = i + 1; j <= n; j++)
			{
				if (a[i] > a[j])
					ans += dp[i][j];
				else
					ans += 1 - dp[i][j];
			}
		printf("%.10f\n", ans);
	}
	return 0;
}