题意：一个答案文件有n行输出，每行是YES或NO，现在给出文件的总字节数s，YES占3字节，NO占2字节。
要求你输出1个文件，且第一行一定是NO，接下来第i行的内容是答案文件第i-1行的内容，问输出正确行数的期望

题解：期望dp，用逆推。dp[i][j][k]表示当前状态为第i行，已经输出了j个YES，这一行要输出YES(0)/NO(1)
因此可以得出，①如果第i要输出YES，那么i+1行如果输出NO，则i的期望值为i+1的期望值加上+1再乘以输出NO的概率；i+1行如果输出YES，则i的期望值为i+1的期望值乘以输出YES的概率。②如果第i行要输出NO，做法和①相同
递推关系式为dp[i][j][0]=dp[i+1][j+1][0]*p1+(dp[i+1][j][1]+1)*p2
                      dp[i][j][1]=(dp[i+1][j+1][0]+1*p1)*p1+dp[i+1][j][1]*p2
因为不能开5000*5000*2的数组，想到第i位只与第i+1位有关，第一维可以滚动。

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int MX = 5e3 + 5;
double dp[2][MX][2];
int main() {int n, s, T;//  freopen ("in.txt", "r", stdin);scanf ("%d", &T);for (int cas = 1; cas <= T; cas++) {scanf ("%d%d", &n, &s);int yes = s - 2 * n;int no = n - yes;memset (dp, 0, sizeof (dp));double ans = 0;for (int i = n - 1; i >= 0; i--) {int ret = n - i, now = i % 2, nxt = (i + 1) % 2;int Max = min (i, yes), Min = max (0, i - no);     //前i个文件中yes的个数为[Min,Max]memset (dp[now], 0, sizeof (dp[now]));for (int j = Min; j <= Max; j++) {double p1 = 1.0 * (yes - j) / ret, p2 = 1.0 * (no - (i - j)) / ret;dp[now][j][0] = dp[nxt][j + 1][0] * p1 + (dp[nxt][j][1] + 1) * p2;dp[now][j][1] = (dp[nxt][j + 1][0] + 1) * p1 +  dp[nxt][j][1] * p2;}}printf ("Case %d: %.7f\n", cas, dp[0][0][0]);//第一行只能输出YES}return 0;
}