注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4405 Aeroplane chess  

2013-08-03 16:51:07|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4405
期望类dp。
推荐一篇比较好的期望类问题求解的博客:http://kicd.blog.163.com/blog/static/126961911200910168335852/
类似博客里的例子,可以推导出这题。
举个例子,比如n=3,m=0
所列方程为dp[0]=1/6*dp[1]+1/6*dp[2]+1/6*dp[3]+1
                 dp[1]=1/6*dp[2]+1/6*dp[3]+1
                 dp[2]=1/6*dp[3]+1
                 dp[3]=0
因为期望就是步数,走了一步所以加1。
于是可以总结,如果m==0,则dp[i]=sigma(dp[i+k]/6)+1;(1<=k<=6),否则dp[i]=dp[f[m]]。

/*
* fudq.cpp
*
* Created on: 2013-08-03
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=100010;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

int n,m,f[N];
double dp[N];

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
int a,b;
while(scanf("%d%d",&n,&m)!=EOF && (n||m))
{
memset(f,-1,sizeof(f));
while(m--)
{
scanf("%d%d",&a,&b);
f[a]=b;
}
dp[n]=0;
for(int i=n-1;i>=0;i--)
{
if(f[i] != -1)
dp[i]=dp[f[i]];
else
{
double s=0;
for(int j=1;j<=6 && i+j <= n;j++)
s+=dp[i+j];
dp[i]=s/6.0+1;
}
}
printf("%.4lf\n",dp[0]);
}
return 0;
}



  评论这张
 
阅读(79)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017