[BZOJ1419] Red is good（期望DP）

传送门

逆推

只不过顺序还是顺着的，思想是逆着的

f[i][j]表示还剩下i张红牌，j张黑牌的期望值

那么边界是

f[i][0]=i，因为只剩i张红牌

f[0][j]=0，只剩黑牌，显然直接停止最优

f[i][j] = max(0,i/(i+j)*f[i1][j]+j/(i+j)*f[i][j1])

空间不够，开两层即可

#include <cstdio>#include <iostream>#define N 5001int n, m;double f[2][N];//逆推，f[i][j]表示还剩下i张红牌，j张黑牌的期望 int main()printf("%.6lf\n", f[n & 1][m]  0.0000005);return 0;}

上一篇：[BZOJ4776] [Usaco2017 Open]Modern Art（差分 + 思维？）

下一篇：[POJ2151]Check the difficulty of problems（概率DP）