HDU4405

以前不是太会求期望的题目,就是做出来的要是靠一知半解的YY出来,昨天多校又碰到了,于是彻底搞了一把,现在算是撸通了。

具体学习资料查看

http://blog.csdn.net/zhoujiachengdhy/article/details/38056765

期望一般从后往前推,全期望公式很重要!<span style="font-family: Arial, Helvetica, sans-serif;">这题的转移方程为dp[i]=((dp[i+1]+dp[i+2]+dp[i+3]+dp[i+4]+dp[i+5]+dp[i+6])/6)+1</span>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 1
vector<int> map[100005];
bool vis[100005];
double dp[100010];
void dfs(int now,double ans)//寻找可以直接抵达的点,标记一下,以后就不用再用递推公式算了
{
    if(map[now].size()==0)
    return ;
    for(int i=0;i<map[now].size();i++)
    {
        if(vis[map[now][i]])
        continue;
        vis[map[now][i]]=true;
        dp[map[now][i]]=ans;
        dfs(map[now][i],ans);
    }
}
int main()
{
	int n,m;
	while(cin>>n>>m && (n|| m))
	{
	    memset(dp,0,sizeof(dp));
	    memset(vis,false,sizeof(vis));
	    for(int i=0;i<m;i++)
	    {
	        int a,b;
	        scanf("%d%d",&a,&b);
	        if(a>b)
	        swap(a,b);
	        map[b].push_back(a);
	    }
	    dfs(n,0);//这里要注意,会有直接到n的情况
	    for(int i=n-1;i>=0;i--)
	    {
	        if(!vis[i])
	        {
	            vis[i]=true;
	            dp[i]=((dp[i+1]+dp[i+2]+dp[i+3]+dp[i+4]+dp[i+5]+dp[i+6])/6)+1;
	            dfs(i,dp[i]);
	        }
	    }
	    printf("%.4f\n",dp[0]);
	    for(int i=0;i<100005;i++)
	    map[i].clear();
	}
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

做股票数据挖掘的一些日志

首先说说数据挖掘吧,接触这东西也是机缘巧合,上学期听说ZYN学姐在做科创,于是问了问具体情况,她说跟数据挖掘有关,这词我还是第一次听说,听起来很高级啊,我看了些...

58250
来自专栏机器之心

2017图灵奖得主:通用芯片每年仅提升3%,神经专用架构才是未来

作者:Norman P. Jouppi, Cliff Young, Nishant Patil, David Patterson

13220
来自专栏AI研习社

DeepMind发布《星际争霸 II》深度学习环境 | 2分钟读论文

来源 / Two Minute Papers 翻译 / 李傲 校对 / 叶俊贤 整理 / 雷锋字幕组 StarCraft II: A New Challenge...

42480
来自专栏CSDN技术头条

BDTC 2014|邢波:Petuum,大数据分布式机器学习平台

【CSDN现场报道】2014年12月12-14日,由中国计算机学会(CCF)主办,CCF大数据专家委员会承办,中科院计算所与CSDN共同协办,以推进大数据科研、...

22480
来自专栏ATYUN订阅号

3D打印全光学固态神经网络,光速执行AI分析

机器学习如今无处不在,但它通常或多或少是不可见的:它们在后台优化音频或识别人脸。但是这个新系统不仅可见,而且是一个物体:它不是通过处理数字而是通过光的衍射来执行...

9420
来自专栏目标检测和深度学习

九大深度学习框架

开源的深度学习神经网络正步入成熟,而现在有许多框架具备为个性化方案提供先进的机器学习和人工智能的能力。那么如何决定哪个开源框架最适合你呢?本文试图通过对比深度学...

39060
来自专栏机器之心

从PyTorch到Mxnet ,对比7大Python深度学习框架

选自kdnuggets 作者:Madison May 机器之心编译 参与:王宇欣、李亚洲 选择什么深度学习框架一直是开发者非常关心的一个话题,而且深度学习框架...

54860
来自专栏逍遥剑客的游戏开发

VR下双手与物体的交互

37060
来自专栏数据小魔方

玩转数据地图系列之——地图上的迷你条形图

最近忙的厉害,产量下降的有点严重,感谢各位还没取关的小伙伴儿。 一周前更新了一篇数据地图上的气泡散点图的内容,不知怎地,这段时间就是跟地图死磕上了,今天还是数据...

40860
来自专栏机器人网

三种人工智能开源框架

TensorFlow是谷歌基于DistBelief进行研发的第二代人工智能学习系统,其命名来源于本身的运行原理。Tensor(张量)意味着N维数组,Flow(流...

21410

扫码关注云+社区

领取腾讯云代金券