poj 1322 Chocolate

引き出しの中にC种の无限の数量のチョコレートがあって、n个を取って机の上に置いて、もし机の上で2つの1种类のチョコレートが现れたら、この2つを食べて、机の上でm块のチョコレートの确率がありますか?確率dp問題:dp[i][j]にi回の操作を行った後、テーブルにj個のチョコレートがある確率を示す.事実によって境界がある:dp[0][0]=dp[1][1]=1.0.私たちは今dp[n][m]を要求することに相当します.私たちはどのように[n][m]状態に達しますか.問題の意味によって2つの方法があります.

n-1回目にチョコレートを取った時にテーブルの上にm+1種類のチョコレートがあり、n回目にテーブルの上と同じ種類のチョコレートを取り出した時、テーブルの上でこの種類と新しく取り出したものを食べて、テーブルの上にmブロックのチョコレートが残っています.すなわちdp[i-1][j+1]がdp[i][j]に移行し、イベントが発生する確率は(j+1)/c

である.

n-1回目にチョコレートを取ったとき、テーブルの上にm-1種類のチョコレートがあり、テーブルとは異なるチョコレートを取り出し、テーブルの上にmブロックを得た.すなわちdp[i-1][j-1]がdp[i][j]に移行し、イベント発生確率は(c-(j-1)/c

である.
以上のように、dp[i][j]=dp[i-1][j-1]*(c-(j-1)/c+dp[i-1][j+1]*(j+1)/c以下にいくつかの最適化点を述べます.そうしないとタイムアウトします.

は、i層目の状態がi層目のみに関係し、配列をスクロールすることを観察することができる.しかし単純にスクロール配列dp[]を用いることはできない.dp[i][j]はj左側のj-1にも関係するし、右側j+1にも関係するし、左右両側にも関係するし、一次元配列は時間的にメンテナンスできないので、dp[2][j]でよく、0と1の切り替えでこの2層の状態を保存する.

偶数回取り、奇数種類のチョコレートが得られず、奇数回取り、偶数種類のチョコレートも得られない.まとめて,(i+j)が奇数の場合,確率は直接0である.確率が0であり、m>c,m>nの場合も含まれる.

チョコレートの種類数は限られていて、テーマの中でN<=1 e 6ですが、精度の要求は3位だけで、Nはある程度大きくて、確率の小数点3位内の値は安定しているので、そんなに大きく計算する必要はありません.私のプログラムでは501内を取って、注意して、nを縮小してもいいですが、nのパリティを変えることはできません.実は変えることができますが、あなたの後ろのdpの前後状態の順序はパリティによって判断されるので、修正しないでください.

最後に、境界dp[i][0]=dp[i-1][1]/cは、テーブル上の0個の確率が前回1個の確率*(1/c)であることを意味し、テーブル上にすでにその1種の確率があることを再取得し、このj=0、dpはこれ以上前から得ることができず、手動で初期化しなければならない.最終コード:

#include 
#include 
#include 
using namespace std;

#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i C || M > N || (M + N) & 1) {
            puts("0.000");
            continue;
        }
        N = min(N, 500 + (N & 1));
        mst(dp, 0);
        dp[0][0] = dp[1][1] = 1.0;

        rep(i, 2, N + 1) {
            int a = i % 2, b = (i + 1) % 2;
            dp[a][0] = dp[b][1] / C;

            for (int j = 1; j <= i && j <= C; ++j) {
                dp[a][j] = dp[b][j - 1] * (C - j + 1.0) / C
                    + dp[b][j + 1] * (j + 1.0) / C;
            }
        }
        printf("%.3lf
", dp[N % 2][M]);
    }
    return 0;
}