首页 > ACM题库 > HDU-杭电 > HDU 4050-wolf5x-动态规划-[解题报告]HOJ
2015
04-16

HDU 4050-wolf5x-动态规划-[解题报告]HOJ

wolf5x

问题描述 :

There are n grids in a row. The coordinates of grids are numbered from x=1 to x=n. Someone starts from x=0. You can step forward with your left leg or right leg alternatively in turn.Namely,if you step forward with your left leg, then you must step with your right leg next. As you can not jump , only one leg is allowed to use each step. Every step you take is in the range of [A,B], inclusively; namely, every step you take is at most B units and at least A units.
Before you start to move, the grids will be initialized randomly with 4 states(0,1,2,3), and p[i][j] means the probability of ith grid initialized with state j. After initialization, the state of the grids will not change.

State 0 means you can’t step into the correspoding grid.
State 1 means you can just step into the grid with your left leg.
State 2 means you can just step into the grid with your right leg.
State 3 means you can step into the grid with either of your legs,and the next step,you can use any legs; namely you don’t need to follow the rules above.
If x>n, then the grid can be stepped in with arbitrary method.means you can step at the place after the nth grid.
For every step,you will choose the “step method” with the minimum step length. Namely, if you can take the step of S units and S+1 units, you will choose the step of S units.
Until you can’t step in any grids in front of you,or you have been in a grid x>n, you will stop.
Can you calculate the expectation of the steps when you stop?

输入:

An integer T means the number of cases.T<=30
For each case,the first line is three integers n,A,B.
The next n lines,each line has 4 number p[i][0], p[i][1], p[i][2], p[i][3].
1 <= A <= B <= n<= 2000.
0 <= p[i][j] <= 1, p[i][0]+p[i][1]+p[i][2]+p[i][3] = 1.

输出:

An integer T means the number of cases.T<=30
For each case,the first line is three integers n,A,B.
The next n lines,each line has 4 number p[i][0], p[i][1], p[i][2], p[i][3].
1 <= A <= B <= n<= 2000.
0 <= p[i][j] <= 1, p[i][0]+p[i][1]+p[i][2]+p[i][3] = 1.

样例输入:

9
2 1 1
0 0.5 0.5 0
0 0 1 0
2 1 1
0 0.5 0.5 0
0.5 0.5 0 0
2 1 2
0 0.5 0.5 0
0 0 1 0
2 1 2
0.2 0.3 0.4 0.1
0.15 0.2 0.25 0.4
3 1 10
0 0 0 1
0 0 0 1
0 0 0 1
3 1 1
0 0 0 1
0 0 0 1
0 0 0 1
3 2 2
0 0 0 1
0 0 0 1
0 0 0 1
3 3 3
0 0 0 1
0 0 0 1
0 0 0 1
3 1 2
0.0 0.3 0.6 0.1
0.1 0.2 0.3 0.4
0.5 0.4 0.1 0.0

样例输出:

2.00000000
1.50000000
2.50000000
2.46000000
4.00000000
4.00000000
2.00000000
2.00000000
2.80200000

做法:忘记看了一个条件,小孩会选择一个最近的落脚点,然后学了点知识,概率累加 可以得出期望

#include<cstdio>
#include<cstring>
/*******
概率与期望之间的关系
在概率论和统计学中,
一个离散性随机变量的期望值(或数学期望、或均值,亦简称期望)
是试验中每次可能结果的概率乘以其结果的总和。
********/
const int LMT=4002;
double dp[LMT][6],p[LMT][6];
int main(void)
{
    int n,a,b,i,j,T;
    double p1,p2,p3,ans;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        memset(p,0,sizeof(p));
        scanf("%d%d%d",&n,&a,&b);
        for(i=1;i<=n;++i)
            scanf("%lf%lf%lf%lf",&p[i][0],&p[i][1],&p[i][2],&p[i][3]);
        ans=0;
        for(i=n+1;i<=n+a;++i)p[i][3]=1.0;
        dp[0][3]=1.0;
        for(i=0;i<=n;++i)
        {
            p1=p2=p3=1.0;
            for(j=i+a;j<=i+b;++j)
            {
                dp[j][2]+=dp[i][1]*p1*p[j][2];
                dp[j][3]+=dp[i][1]*p1*p[j][3];
                p1*=(p[j][0]+p[j][1]);
                dp[j][1]+=dp[i][2]*p2*p[j][1];
                dp[j][3]+=dp[i][2]*p2*p[j][3];
                p2*=(p[j][0]+p[j][2]);
                dp[j][1]+=dp[i][3]*p3*p[j][1];
                dp[j][2]+=dp[i][3]*p3*p[j][2];
                dp[j][3]+=dp[i][3]*p3*p[j][3];
                p3*=p[j][0];
            }
        }
        for(i=a;i<=n+a;++i)
            for(j=1;j<4;++j)
                ans+=dp[i][j];
            printf("%.8f\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/cqlf__/article/details/8865482


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。