codevs 1060 개그 운동회 dp

1060 개그 월 드 컵
Time Limit: 20 Sec  Memory Limit: 256 MB
제목 연결http://codevs.cn/problem/1060/
Description
  월 드 컵 조별 리그 가 끝나 면서 프랑스, 아르헨티나 등 세계 강팀 들 이 줄줄 이 탈락 해 가슴 이 아 팠 다.
사람들 은 개그 월 드 컵 을 조직 하여 탈락 한 강팀 들 을 다시 조직 하여 월 드 컵 과 함께 시합 하 게 하 였 다. 너 와 너의 친구.
친구 들 은 기꺼이 티켓 을 사 러 갔다. 그러나 코믹 월 드 컵 의 티켓 판매 방식 도 특별 하 다. 그들 은 두 가지 티켓 만 준비 했다. A 류.
표 --- 무료 구기 표 B 류 표 --- - 두 배의 가격 구기 표. 구 매 할 때 직원 이 동전 을 던 져 서 결정 하고 정면 으로 던진다.
A 류 표를 사고, 반대로 B 류 표를 삽 니 다. 그리고 시장 경제 이기 때문에 주최측 이 돈 을 거꾸로 붙 일 수 없 기 때문에 그들 은 항상 준비 합 니 다.
같은 A 류 표 와 B 류 표 가 많 습 니 다. 당신 과 당신 의 친 구 는 운 좋게 도 어떤 멋 진 경기 의 마지막 두 자리 에 섰 습 니 다.
이때 스 태 프 들 은 동전 을 통 해 표를 팔기 시작 했다. 그러나 더욱 운 이 좋 은 것 은 스 태 프 들 이 당신들 앞 에 왔 을 때 그 는 이미 필요 없다 는 것 을 알 게 되 었 다 는 것 이다.
나머지 두 장의 표 는 모두 무료 이기 때문에 동전 을 더 던 졌 다.
 
    너 와 너의 친 구 는 기뻐 하 는 나머지, 줄 뒤에 서 있 는 두 사람 이 동시에 한 표를 받 을 확률 이 얼마 인지 계산 하고 싶다.
(A 류 표 나 B 류 표를 동시에 받 는 것 포함) 스 태 프 들 이 2n 장의 티켓 을 준비 했다 고 가정 하면 그 중에서 n 장의 A 류 표, n 장의 B 류 표, 그리고 팀 에 있 는 사람 은 각자 반드시 한 장의 티켓 만 살 수 있다 (A 를 사 든 B 를 사 든).
A 의 한 단락 이 완전히 겹 치 거나 상하 좌우 의 평행 이동 을 거 쳐 접선 A 의 한 단락 과 완전히 겹 칠 수 있다 는 것 은 추 실 형님 이 여동생 의 멜로디 일 부 를 불 었 다 는 뜻 이다.
Input
입력 파일 은 한 줄 에 불과 합 니 다. 구표 수 2n 을 포함 합 니 다. 그 중에서 0 < n < = 1250, n 은 정수 입 니 다.
Output
    출력 파일 은 하나의 숫자 만 포함 하고 같은 표를 받 을 확률 을 위해 소수점 뒤의 4 자리 까지 정확 합 니 다.
 
Sample Input
256
Sample Output

0. 9500

HINT
 
제목
 
문제 풀이:
전 i 명 이 A 표를 받 을 확률
전이 방정식

    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]*0.5;
        for(int j=1;j<=n/2;j++)
        {
            if(j==n/2)
                dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]*0.5;
        }
    }

 
코드:
 

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200001
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
/*

inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
*/
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
//**************************************************************************************

double dp[3000][3000];
int main()
{
    int n=read();
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]*0.5;
        for(int j=1;j<=n/2;j++)
        {
            if(j==n/2)
                dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]*0.5;
        }
    }
    printf("%.4lf
",dp[n-2][n/2]*2);
}