codejam 2008 APAC local onsites C確率dp

リンク:https://code.google.com/codejam/contest/32005/dashboard#s=p2確率dpは本当に分からない.勉強するしかない.解法:まずこの問題が連続的な問題であることを発見します.あなたの賭けは任意で、小数でもいいからです.しかし、最も簡単な状況から分析することができます.1ラウンドしかないときから分析すると,1)手に100 wのお金があれば1の確率で家に持ち帰ることができ,2)手に50 w未満のお金があれば,どうしても家に持ち帰ることができず,確率は0である.3)50 w~100 wの間なら、お金を全部押して、勝ったら家に持ち帰ることができ、負けたらできない.確率はpです.この時、2ラウンドの状況を分析します.1)25 w未満の確率は0である.2)25 wから50 wの間で、上が1ラウンドしかない時の3番目のケースに帰約できることを発見したら、手に持っているお金を投げて、倍になったら上の3番目のケースになって、投げて、勝ったら家に持って帰ることができます.確率p*p.この場合、上記の各状況について(直接持ち帰る場合を除く)とも2つのケースに分けて上にまとめることができます.50 w~100 wは2つのケースに分けられ、50~75,75~100です.これで合計5つのケースがあり、m輪に対応していることが判明し、2 m+1というように多様なケースがあります.ある場合の範囲内での確率は同じで、具体的な金額がいくらであっても連続的に離散に変換することに成功します.それぞれの状況については、前のラウンドのいくつかの状況から移行することができます.前のホイールと現在のホイールを記録するスクロール配列が必要です.dpを定義し[2][2]、それぞれの状況に対してすべての可能性を遍歴し、その中の最大値を求めることが、現在の状況の最大確率で学ぶ方法である:難題に対して入手点が見つからない場合、できるだけ最も簡単な状況を選んで分析を開始し、もう少し複雑なものを見て、より簡単な状況に帰約できるかどうかを考える.少しも考えがないのを避ける.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000000
typedef long long ll;
int n;
int m,x;
double p;
double dp[2][1<<15+1];
void slove()
{
    n = 1 << m;
    fill(dp[0],dp[0]+n,0);
    fill(dp[1],dp[1]+n,0);
    dp[1][n] = 1.0;
    for(int k = 0;k < m;k++) //     
    {
        for(int i = 0;i <= n;i++) //     
        {
            double t = 0.0;
            for(int j = 0;;j++) //      
            {
                if(i+j > n || i-j < 0) break;
                t = max(t,p*dp[(k+1)&1][i+j]+(1-p)*dp[(k+1)&1][i-j]);//      
            }
            dp[k&1][i] = t;
        }
    }
    int ans = (ll)x * n / M; //         
    printf("%.6f
",dp[(m-1)&1][ans]);
}
int main()
{
    freopen("C-large-practice.in","r",stdin);
    freopen("out1.txt","w",stdout);
    int t;
    scanf("%d",&t);
    int kase = 1;
    while(t--)
    {
        scanf("%d %lf %d",&m,&p,&x);
        printf("Case #%d: ",kase++);
        slove();
    }
    return 0;
}