TopCoder9915（期望dp）

1.还是逆向。

2.状态是还剩红i黑j张时的期望，这样从0，0往R，B推。注意因为是逆着的，所以到了某一步发现期望为负时直接f[i][j]归零，意义是这之后（在递推中算是这之前）的都不摸了，到这就停（根据题意随时可以停手），所以相当于是从这个时候开始摸，所以为0.

3.滚动数组因为是无视j的，所以j和j-1要无形中体现出来，所以j放外层循环。

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef double db;

 const int maxn = ;

 class RedIsGood {

     public:

         db f[maxn];

         db max(db a, db b) {

             return a > b ? a : b;

         }

         db getProfit(int R, int B) {

             for (int i = ; i <= R; i++)    f[i] = i;

             for (int j = ; j <= B; j++) {

                 for (int i = ; i <= R; i++) {

                     f[i] = max(, (db)(f[i - ] + ) * i / (i + j) + (db)(f[i] - ) * j / (i + j));

                 }

             }

             return f[R];

         }

 };

巴特西

TopCoder9915（期望dp）

最新文章

热门文章