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]【数学期望】【动态规划】  讨论


Get start with &quot;Redis&quot; —— by “EOF”

Get start with Redis 怎么安装Redis的 tutorial一堆~我不重复了,仅仅留下自己开始玩Redis的经验(LZ 数据库零经验,So...一切从零开始学Redis) 在shell下触发redis-server就启动Redis了. 我一开始傻乎乎的~好郁...

Redis 实践笔记

最近在项目中实践了一下Redis,过程中遇到并解决了若干问题,记录之. Why Redis 我们这个项目是对原有缓存系统的改进,应用场景是论坛发帖,回帖,置顶,以及操作日志等等;原有系统会有替换算法把内...

redis 命令行 操作

redis目前提供四种数据类型:string,list,set及zset(sorted set)。 * string是最简单的类型,你可以理解成与Memcached一模一个的类型,一个key对应一个value,其上支持的操作与Memcached的操作类似。但它的功...

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