HDU-4405 Aeroplane chess 期望DP-白红宇

HDU-4405 Aeroplane chess 期望DP

阅读量：5769 次

发布时间：2019-06-18

本文共 1090 字，大约阅读时间需要 3 分钟。

dp[i]表示第i个位置跳出去的期望天数，先构造出N+1到N+5这几个位置，然后先把dp[N-N+5]这六个位置全部赋值为0，因为这几个位置都已经出去了。

然后就是递推了

如果该点没有航班的话：

dp[x] = (1/6)*(dp[x+1] + dp[x+2] + dp[x+3] + dp[x+4] + dp[x+5] + dp[x+6]) + 1;

否则：

dp[x] = dp[link[x]]; 其中link[x]表示x连到哪一个点。

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #define MAXN 100020#define LL long longusing namespace std;int N, M;const double EE = 1.0/6;double dp[MAXN];int link[MAXN];int main( ){ int len, a, b; while (scanf("%d %d", &N, &M) == 2) { len = N+5; memset(link, 0xff, sizeof (link)); for (int i = N; i <= len; ++i) dp[i] = 0; for (int i = 1; i <= M; ++i) { scanf("%d %d", &a, &b); link[a] = b; } for (int i = N-1; i >= 0; --i) { double temp = 0.0; if (link[i] != -1) { temp = dp[link[i]]; } else { for (int j = i + 1; j <= i + 6; ++j) { temp += EE * dp[j]; } temp += 1; } dp[i] = temp; } printf("%.4lf\n", dp[0]); } return 0;}