POJ 1322 Chocolate：概率 DP 求剩餘巧克力分布

解釋：

• 從 j-1 狀態轉移：抽到新顏色，概率 (c-(j-1))/c
• 從 j+1 狀態轉移：抽到已有顏色配對消失，概率 (j+1)/c

代碼實現

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

double dp[1010][1010];

int main() {
    int c, n, m;
    while (~scanf("%d", &c), c) {
        scanf("%d%d", &n, &m);
        if (m > c || m > n || (n+m)%2) { printf("0.000\n"); continue; }
        if (n > 1000) n = 1000 + n%2; // 穩態截斷
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = dp[i-1][1] / c;
            dp[i][c] = dp[i-1][c-1] / c;
            for (int j = 1; j < c; ++j)
                dp[i][j] = dp[i-1][j-1]*(c-j+1)/c + dp[i-1][j+1]*(j+1)/c;
        }
        printf("%.3lf\n", dp[n][m]);
    }
    return 0;
}

優化技巧

• n > 1000 時，概率分布趨於穩態，截斷 n 為 1000 或 1001（保持奇偶性）
• 邊界 j=0 和 j=c 單獨處理
• 輸出保留 3 位小數