codeforces 351B B. Jeff and Furik(확률)

제목 링크:

codeforces 351B

제목 대의:

한 게임을 주고 먼저 한 쌍의 인접한 수 교환 위치를 선택한 다음에 랜덤으로 한 쌍의 수를 찾은 다음에 동전을 던져 교환 여부를 결정한다. 교환할 수 없으면 다시 찾는다.가장 좋은 전략을 취할 수 있는 대략적인 서열에 대한 기대를 묻는다.

제목 분석:

4

dp[i]를 정의하면 i개의 역순으로 대응하는 걸음의 기대를 감소시킨다

dp[i]=1+1+dp[i−2]⋅0.5+dp[i−1+1]]⋅0.5

4

먼저 선택할 수 있기 때문에 매번 조작을 해서 역순을 줄인다

4

우리는 dp[i]=4+dp[i-2], dp[0]=0, dp[1]=1을 얻었다

AC 코드:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 3007

using namespace std;

int n,a[MAX];

int main ( )
{
    while ( ~scanf ( "%d" , &n ) )
    {
        for ( int i = 0 ; i < n ; i++ )
            scanf ( "%d" , &a[i] );
        int m = 0;
        for ( int i = 1 ; i < n; i++ )
            for ( int j = 0 ; j < i ; j++ )
                if ( a[j] > a[i] ) 
                    m++;
        int ans = 0;
        if ( m&1 )
            ans = 1 + m/2*4;
        else ans = m*2;
        printf ( "%.7f
" , (double)ans );
    }
}