LightOJ-1274 期望DP

题目链接：https://vjudge.net/contest/76505#problem/I
题目大意：
一个答案文件有n行输出，每行是YES或NO，现在给出文件的总字节数s，YES占3字节，NO占2字节。
要求你输出1个文件，且第一行一定是YES，接下来第i行的内容是答案文件第i-1行的内容，问输出正确行数的期望。

思路：因为第一个一定是YES正着不好DP。我们用f[i][j][k]:前i个还有j个YES没有出现，并且i+1的猜的是k的方案数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

double f[2][5005][2];
int main(){

    int t, cas=0; scanf("%d", &t);
    while(t--){
        int n, s; scanf("%d%d", &n, &s);
        int yes=s-2*n, no=n-yes;
        memset(f, 0 ,sizeof(f));
        for(int i=n-1; i>=0; i--){
            int MAX=min(i, yes), MIN=max(i-no, 0);
            int now=i%2;
            memset(f[now], 0, sizeof(f[now]));
            for(int j=MAX; j>=MIN; j--){//yes可取的范围
                double p1=(yes-j)*1.0/(n-i), p0=(no-(i-j))*1.0/(n-i);//放yes和no的概率
                //cout<<p1<<" "<<p0<<endl;;
                f[now][j][0]=f[now^1][j][0]*p0+(f[now^1][j+1][1]+1)*p1;//因为i+1实际上出现的数据一定是i+1猜的
                f[now][j][1]=(f[now^1][j][0]+1)*p0+f[now^1][j+1][1]*p1;
                //cout<<f[i][j][0]<<" "<<f[i][j][1]<<endl;
            }
        }
        printf ("Case %d: %.7f\n", ++cas, f[0][0][1]);//第一个一定是YES
    }

    return 0 ;
}