频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
[TopCoder SRM420 Div1 500pt RedIsGood]
2015-09-25 10:48:26         来源:加贝木苇的BLOG  
收藏   我要投稿
【题意】

桌面上有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 
#include 
#include 
#include 
#include 

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
,dp[B]);
    } return 0;
}


 

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:如何封装form表单中富文本编辑器bootstrap wysiwyg到jfinal传递参数
下一篇:牛X素材推荐之MaterialTextField
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站