hdu4405--Aeroplane chess+機率期望dp

首先推薦一篇很好的如何機率期望問題的入門文章：點選打開連結

昨天比賽的時候面對這道題的第一想法是依照數學期望的定義來做，即依次求出某個點扔i次骰子能到達n點的機率，然後由期望的定義就可以求出答案了。但顯然這在程式上是不可能實作的。

今天看了那篇文章後才知道自己的想法是大錯特錯的;求解這種問題應該采用一種遞推的思路，即每次隻考慮一次轉移後目前狀态的期望，然後我們依次考慮每個節點就可以得到一個方程組，然後就隻需要求解這個方程組就行了。

當然對于如何求解這個方程組，我們可以采用高斯消元法，當然如果這個方程是遞推形式的（如這個題）我們可以直接遞推求解就行。

下面就以題目的樣例一具體解說一下求解過程

定義Ei表示第i個點到達第n點及其以後點的期望

對于第一個樣例n=2

E0=1/6*E1+1/6*E2+1 (加1是因為這是再第一個點扔了一次骰子後的情況，另外E3---E6都是等于E2=0的，是以不寫)

E1=1/6*E2+1

然後我們知道E2=0 是以隻要先求出E1然後再求出E0就行，即求解過程就是一個倒退的過程。

最後對于這個題目，還定義了一種”飛行線“,對于這個情況，如果某個點直接和其後面的點相連，那麼它的期望就等于後面那個點的期望不需要進行狀态轉移。

代碼如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

double f[100010];
int m[100010];

int main()
{
     int n,k;
     while(scanf("%d%d",&n,&k))
     {
             if(n+k==0)
                 break;
             memset(m,-1,sizeof(m));
             for(int i=0;i<k;i++)
             {
                    int x,y;
                    scanf("%d%d",&x,&y);
                    m[x]=y;
             }
             memset(f,0,sizeof(f));
             for(int i=n-1;i>=0;i--)
             {
                    if(m[i]!=-1)
                       f[i]=f[m[i]];
                    else
                    {
                         for(int j=1;j<=6;j++)
                         {
                               if(i+j<=n)
                                  f[i]+=1.0/6*f[i+j];
                         }
                         f[i]+=1.0;
                    }
             }
             printf("%.4lf\n",f[0]);
     }
   return 0;
}