読者です 読者をやめる 読者になる 読者になる

Coreforces #157 Div1 D. Little Elephant and Broken Sorting

n,m=1000なのでnmかな〜〜と言った感じで考えてたら解けました
結局O(nm)ですね多分
汚いプログラムになってしまいましたが、
dp[i][j](i<j):その時に考えられる数列のパターン(2^m通り)のなかで、i番目がj番目より大きくなっている物の可能性、割合

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

const int MAX_N = 1001;
int main(int argc, char *argv[]) {
    int n, m;
    scanf("%d %d", &n, &m);
    double dp[MAX_N][MAX_N] = {};
    int d[MAX_N];
    for (int i = 0; i < n; i++) {
        scanf("%d", &(d[i]));
    }
    for (int x = 0; x < n; x++) {
        for (int y = x+1; y < n; y++) {
            if (d[x] > d[y]) {
                dp[x][y] = 1.0f;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        if (a > b) {
            swap(a, b);
        }
        dp[a][b] = 0.5f;
        for (int j = 0; j < a; j++) {
            dp[j][a] = dp[j][b] = (dp[j][a] + dp[j][b]) / 2;
        }
        for (int j = a+1; j < b; j++) {
            double dpa = dp[a][j], dpb = dp[j][b];
            dp[a][j] = (dpa + (1 - dpb)) / 2;
            dp[j][b] = ((1 - dpa) + dpb) / 2;
        }
        for (int j = b+1; j < n; j++) {
            dp[a][j] = dp[b][j] = (dp[a][j] + dp[b][j]) / 2;
        }
    }
    double r = 0;
    for (int x = 0; x < n; x++) {
        for (int y = x+1; y < n; y++) {
            r += dp[x][y];
        }
    }
    printf("%.10f\n", r);
    return 0;
}