Codeforces 513G1 513G2 Inversions problem 概率dp - c++编程基础

TOP

Codeforces 513G1 513G2 Inversions problem 概率dp

2015-07-20 17:19:34 来源: 作者: 【大中小】浏览:2次

Tags：Codeforces 513G1 513G2 Inversions problem 概率

题目链接：点击打开链接

题意:

给定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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 5172 GTY's gay friends..	下一篇：hdu 3565 Bi-peak Number 数位dp

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: