lightoj1274(數學機率與期望)

看了http://blog.csdn.net/guard_mine/article/details/45824343

用一個三維資料dp[i][j][flag]  記錄在第i個位置,前面已經有j個yes,并且前一個是yes\no時的期望錯誤次數;

因為位置那一維直接開會爆記憶體,是以用滾動數組;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

double dp[2][5010][2];
int m1, m2;
int main() {
    int t;
	int cas = 1;
    scanf("%d", &t);
    while (t--) {
        int n, s;
        scanf("%d%d", &n, &s);
        m1 = s - 2 * n;
        m2 = 3 * n - s;
        dp[n % 2][m1][0] = dp[n % 2][m1][1] = 0;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = min(m1, i); j >= 0 && i - j <= m2; --j) {
                double p1 = (m1 - j) * 1.0 / (n - i);
                double p2 = (m2 - (i - j)) * 1.0 / (n - i);
                if (j + 1 <= m1) {
                    dp[i % 2][j][0] = dp[(i + 1) % 2][j + 1][0] * p1 + (dp[(i + 1) % 2][j][1] + 1) * p2;
                    dp[i % 2][j][1] = (dp[(i + 1) % 2][j + 1][0] + 1) * p1 + dp[(i + 1) % 2][j][1] * p2;
                }
                else {
                    dp[i % 2][j][0] = (dp[(i + 1) % 2][j][1] + 1) * p2;
                    dp[i % 2][j][1] = dp[(i + 1) % 2][j][1] * p2;
                }
            }
        }
        printf("Case %d: %.12f\n", cas++, dp[0][0][0]);
    }
    return 0;
}