【dp】cf 513G2

题目链接：http://codeforces.com/problemset/problem/513/G2

题目大意：给定有n个数的一个数列，每次操作是等概率翻转一个区间，这样操作k次，求逆序数对个数的期望。
（1 ≤ n ≤ 30, 1 ≤ k ≤ 200）
思路：

f[k][i][j] 表示k次翻转以后a[i] 在a[j] 前面的概率,初始化条件是 f[0][i][j] = 1 f[0][j][i] = 0 ( i < j )

另外翻转区间 [i, j]的概率P = 1 / ( n * (n+1)  / 2)

由于 翻转时[i, j]内元素位置都会交换，

所以枚举翻转时的要循环枚举区间内所有的元素的转移情况

（可以滚动……）

代码：

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
const int N = 110;
int n, k;
double f[2][N][N];
double tmp[N][N];
int a[N];


void dp()
{
    double p = 1.0 * n * (n + 1) / 2.0;
    for (int tt = 1; tt <= k; tt++)
    {
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            f[tt % 2][i][j] = 0;
        for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
        for(int x = 1; x <= n; x++)
        for(int y = x; y <= n; y++)
        {
            int a = i, b = j;
            if(x <= i && i <= y) a = x + y - a;
            if(x <= j && j <= y) b = x + y - b;
            if(a > b) swap(a, b);
            if(x <= i && j <= y) f[tt % 2][a][b] += (1.0 - f[(tt - 1) % 2][i][j]) / p;
            else f[tt % 2][a][b] += 1.0 * f[(tt - 1) % 2][i][j] / p;
        }
    }
}

int main()
{
    while(scanf("%d%d",&n, &k) != EOF)
    {
        double re = 0;
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

        memset(f, 0, sizeof(f));
        for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            f[0][i][j] = 1.0;

        dp();

        for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
        {
            if(a[i] > a[j]) re += f[k % 2][i][j];
            else re += 1.0 - f[k % 2][i][j];
        }
        printf("%.15f\n", re);
    }
    return 0;
}