Codeforces 513G1 513G2 Inversions problem [概率dp]-白红宇

Codeforces 513G1 513G2 Inversions problem [概率dp]

阅读量：6579 次

发布时间：2019-06-24

本文共 2231 字，大约阅读时间需要 7 分钟。

转自九野：http://blog.csdn.net/qq574857122/article/details/43643135

题目链接：

题意:

给定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]内元素位置交换，枚举这次翻转的区间时所有的转移情况

	2015-02-17 07:09:26			GNU C++	Accepted	217 ms	200 KB

2015-02-17 07:09:26

GNU C++

Accepted

217 ms

200 KB

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
             9 #include
             
               10 #include
              
                11 #include
               
                 12 13 #define N 105 14 #define M 10005 15 //#define mod 10000007 16 //#define p 10000007 17 #define mod2 1000000000 18 #define ll long long 19 #define ull unsigned long long 20 #define LL long long 21 #define eps 1e-6 22 //#define inf 2147483647 23 #define maxi(a,b) (a)>(b)? (a) : (b) 24 #define mini(a,b) (a)<(b)? (a) : (b) 25 26 using namespace std; 27 28 int n; 29 int k; 30 double dp[N][N]; 31 double ans; 32 double p; 33 double tmp[N][N]; 34 int v[N]; 35 36 void ini() 37 { 38 ans=0; 39 int i,j; 40 for(i=1;i<=n;i++){ 41 scanf("%d",&v[i]); 42 } 43 p=1.0*n*(n+1)/2.0; 44 memset(dp,0,sizeof(dp)); 45 for(i=1;i<=n;i++){ 46 for(j=i+1;j<=n;j++){ 47 dp[i][j]=1.0; 48 } 49 } 50 } 51 52 void solve() 53 { 54 int i,j,x,y,a,b; 55 while(k--){ 56 memcpy(tmp,dp,sizeof(dp)); 57 memset(dp,0,sizeof(dp)); 58 for(i=1;i<=n;i++){ 59 for(j=i+1;j<=n;j++){ 60 for(x=1;x<=n;x++){ 61 for(y=x;y<=n;y++){ 62 a=i;b=j; 63 if(x<=i && i<=y) a=x+y-a; 64 if(x<=j && j<=y) b=x+y-b; 65 if(a>b) swap(a,b); 66 if(x<=i && j<=y){ 67 dp[a][b]+=(1.0-tmp[i][j])/p; 68 } 69 else{ 70 dp[a][b]+=1.0*tmp[i][j]/p; 71 } 72 } 73 } 74 } 75 } 76 } 77 } 78 79 void out() 80 { 81 int i,j; 82 for(i=1;i<=n;i++){ 83 for(j=i+1;j<=n;j++){ 84 if(v[i]>v[j]){ 85 ans+=dp[i][j]; 86 } 87 else{ 88 ans+=1.0-dp[i][j]; 89 } 90 } 91 } 92 printf("%.10f\n",ans); 93 } 94 95 int main() 96 { 97 //freopen("data.in","r",stdin); 98 //freopen("data.out","w",stdout); 99 //scanf("%d",&T);100 //for(int ccnt=1;ccnt<=T;ccnt++)101 //while(T--)102 //scanf("%d%d",&n,&m);103 while(scanf("%d%d",&n,&k)!=EOF)104 {105 ini();106 solve();107 out();108 }109 return 0;110 }