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


Memcached, Redis, MongoDB三者比较

Memcached, Redis, MongoDB关于这三者,很多朋友还经常把他们搞混淆,其实这三者还是有区别的: mongodb和memcached不是一个范畴内的东西。mongodb是文档型的非关系型数据库,其优势在于查询功能比较...

初识redis

redis是个存储服务,能够支持k-v等结构,数据能落地(memcache的数据是内存数据,无法落地) 下面进入redis的世界来一探究竟。 命令行进入redis: 用ps aux | grep redis看下redis-server是否开启,对应...

Redis数据导入工具优化过程总结

Redis数据导入工具优化过程总结 背景 使用C++开发了一个Redis数据导入工具 从oracle中将所有表数据导入到redis中; 不是单纯的数据导入,每条oracle中的原有记录,需要经过业务逻辑处理, 并添加...

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