POJ 3756 Chess Game【DP求期望】

核心算法

DP

分析

  1. graph[i]记录在格子i处前进的步数
  2. stop[i]标记在格子i处是否停一次
  3. 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;
}