核心算法
DP
分析
- graph[i]记录在格子i处前进的步数
- stop[i]标记在格子i处是否停一次
- dp[i][j]表示第j部到达格子i的概率
则 初始化下dp[0][0]=1;
若已知dp[i][j],现在掷骰子得点数为k,移动到格子curto = i+k;
如果格子curto处为暂停,则将当前概率加至dp[curto][i+2]处
否则,curto 首先根据graph[curto]信息移动,将概率加至相应位置dp[curto][i+1]即可
ans = sum(dp[n][i]*i)(i=0,1,2,…N)
PS:当ans = 0时输出Impossible!
Answer
#include<stdio.h>
#include<string.h>
const int N = 1001;//最多需要步数
const int M =105;//格子数
int graph[M];//表示第i格是前进还是后退
bool stop[M];//表示该格是否该停一次
double dp[M][N];//dp[i][j]表示第j步到达第i格的概率
int main()
{
int nf,ns,nb,n,id,step;
while(scanf("%d",&n)!=EOF) {
memset(graph,0,sizeof(graph));
memset(stop,false,sizeof(stop));
memset(dp,0,sizeof(dp));
dp[0][0]=1;//第0步在0格的概率为1
scanf("%d",&nf);//前进信息
while(nf--){scanf("%d%d",&id,&step);graph[id]+=step;}
scanf("%d",&nb); //后退信息
while(nb--){
scanf("%d%d",&id,&step);
graph[id]-=step;
}
scanf("%d",&ns);//暂停信息
while(ns--) {
scanf("%d",&id);
stop[id]=true;
}
double once = 1.0/6;
int i,j,k;
for(i=1;i<N;i++) {
for(j=0;j<n;j++) {
if(dp[j][i-1]==0)
continue;
for(k=1;k<=6;k++) {
double top = once*dp[j][i-1];
int curto = k+j;
if(curto>n) {
curto = 2*n-curto;
}
if(stop[curto])//暂停
{
dp[curto][i+1]+=top;
continue;
}
curto+=graph[curto];
if(curto>n)
curto = 2*n-curto;
if(curto<0)curto=-curto;
dp[curto][i]+=top;
}
}
}
double ans = 0;
for(i=0;i<N;i++) {
ans+=dp[n][i]*i;
}
if(ans>0)
printf("%.2lf\n",ans);
else
printf("Impossible\n");
}
return 0;
}