HDU-4405 Aeroplane chess 期望DP

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<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<vector>
#include<string>
#define MAXN 100020
#define LL long long
using 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;
}

优质内容筛选与推荐>>
1、cv2.bilateralFilter 双边滤波
2、wp8 longlistselector 动态加载datatemplate
3、线程的基本概念、线程的基本状态以及状态之间的关系
4、SPOJ 10570 LONGCS - Longest Common Substring
5、前端方面值得尊敬的大神们

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看