ItGo.me - 专注IT技术分享

首页 > Redis > [TopCoder SRM420 Div1 500pt RedIsGood]【数学期望】【动态规划】

[TopCoder SRM420 Div1 500pt RedIsGood]【数学期望】【动态规划】

时间:2016-08-28来源:网友分享 点击:
【题意】

桌面上有R 张红牌和B 张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到1 美元,黑牌则付出1 美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。

【思路】:



于是dp[0][0]=0
dp[i][j]=F[i-1][j]+1;     (j=0)
dp[i][j]=0;               (i=0)
dp[i][j]= max(0.0,(dp[i-1][j]+1)*(i/(i+j))  +  (dp[i][j-1])*(j/(i+j)));
最后dp[R][B]就是期望.

原题好像要用滚动数组优化,代码如下:

#include <math.h>#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;const double eps=1e-5;const double pi= acos(-1.0);const int N = 1e5+10;double dp[N];int main(){int R,B;while(cin>>R>>B){memset(dp,0,sizeof(dp));for(int i=1; i<=R; ++i){dp[0]=i;for(int j=1; j<=B; ++j){dp[j]=max(0.0,(dp[j-1]-1)*(1.0*j/(i+j))+(dp[j]+1)*(1.0*i/(i+j)));}}printf("%.3f\n",dp[B]);} return 0;}


版权声明:本文为博主原创文章,未经博主允许不得转载。

[TopCoder SRM420 Div1 500pt RedIsGood]【数学期望】【动态规划】

[TopCoder SRM420 Div1 500pt RedIsGood]【数学期望】【动态规划】  讨论


Webdis - 一个快速的 Redis HTTP 接口

Webdis是一个简单的 HTTP 服务器。它将操作命令转发至Redis,然后按你选择的格式送发请求返回。它用到了 , , , 和 这些第三访包。支持以下特性: 支持GET 和 POST,和 PUT用于文件上传 默认返回输...

Redis 在 Windows 下的原型版本 - Redis on Windows

Redis on Windows 是 Redis 在 Windows 下的原型版本,基于 Redis 2.4.11,支持 64 位 Windows。 编译方法: 使用 Visual Studio 10 打开 msvs\redisserver.sln 文件并进行构建 构建成功后将在 msvs\$(Configuration) 目录下生...

Redis与Memcached比较

Redis Memcached 特性,技术选型时需要注意到的问题。 如果简单地比较Redis与Memcached的区别,大多数都会得到以下观点: 1 Redis不仅仅支持简单的k/v类型的数据,同时还提供list,set,hash等数据结构...

【题意】 桌面上有R 张红牌和B 张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到1 美元,黑牌则付出1 美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。 【
------分隔线----------------------------