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种途径：

1. 在第n-1次取巧克力时桌上已有m+1种巧克力，第n次取时取出一个与桌上同种的巧克力，此时吃掉桌上该种与新取出来的，桌上剩余m块巧克力。
   即dp[i-1][j+1] 转移到 dp[i][j]，事件发生的概率为(j+1)/c
2. 在第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
下面叙述几个优化点，否则会超时：

1. 可以观察到第i层状态只由第i-1层有关，滚动数组。但是不能简单的用滚动数组dp[]，因为dp[i][j]既和j左侧的j-1有关，也和右侧j+1有关，和左右两侧相关，一维数组在时间上是无法维护的，所以用dp[2][j]即可，利用0和1的切换来保存这2层的状态。(一层不行，那就两层)
2. 偶数次取，无法得出奇数种巧克力，奇数次取，也无法得出偶数种巧克力。总结一下，(i+j)为奇数时，概率直接为0。概率为0的，还包括m>c，m>n的情况。
3. 巧克力的种类数是有限的，题目里N<=1e6，但是精度要求只是3位，N大到一定程度，概率的小数点3位内的值趋于稳定，所以不必真算那么大，我程序里取到501内，注意，缩小n可以，但是不能改变n的奇偶性。其实是可以改变的，但是因为你后面dp的先后状态的顺序还是根据奇偶性来判断的，所以别修改。

最后留意一点:
边界dp[i][0] = dp[i - 1][1] / c，意思是桌上0个的概率是上次1个的概率*(1/c)，即再取桌上已有那1种的概率，这个j = 0，dp无法再从前面得到，必须手动初始化。
最终代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
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<(b);++i)
const int inf = 0x3f3f3f3f, maxM = 1e6 + 5;
int N, M, C;
double dp[2][maxM];
// dp[i][j] = dp[i-1][j-1]*(c-j+1)/c + dp[i-1][j+1]*(j+1)/c

int main() {
    // freopen("data.in", "r", stdin);
    while (~scanf("%d", &C) && C) {
        scanf("%d%d", &N, &M);
        if (M > 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\n", dp[N % 2][M]);
    }
    return 0;
}