LightOJ 1030 Discovering Gold + Hdu4405 Aeroplane chess (期望)

妖狐艹你老母 2021-11-04 10:28 220阅读 0赞

相似的两题一起总结。

**LightOJ 1030 Discovering Gold**

题目链接：http://lightoj.com/volume\_showproblem.php?problem=1030

题意：投骰子从1走到n，注意在最后如果数字超过剩余的格数要重新投。

思路：倒推,dp\[i\]表示走到i位置(从1开始计数)之后获得的期望

#include <cstdio>
    #include <cstring>
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=105;
    int data[N];
    double dp[N];
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,i,n;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		memset(dp,0,sizeof(dp));
    		scanf("%d",&n);
    		for (i=1;i<=n;i++)
    			scanf("%d",&data[i]);
    		dp[n]=data[n];
    		for (int i=n-1;i>0;i--)
    		{
    			int d=min(6,n-i);
    			dp[i]=data[i];
    			for (int j=1;j<=d;j++)
    				dp[i]+=dp[i+j]/d;
    		}
    		printf("Case %d: %.10lf\n",Cas,dp[1]);
    	}
    	return 0;
    }
    
    /*
    4
    6
    1 2 3 4 5 6
    7
    1 2 3 4 5 6 7
    8
    1 2 3 4 5 6 7 8
    12
    2 3 5 7 11 13 17 19 23 29 31 37
    
    Output
    Case 1: 11.98333333
    Case 2: 14.60000000
    Case 3: 18.72500000
    Case 4: 94.16124614
    */

**Hdu4405 Aeroplane chess**

与上一题差不多，第一个不同点是有捷径：直接从a跳到b,不需要投骰子的，直接标记一下，a的期望值也就等于b的期望值。(a<b)

第二个不同点：在最后如果数字超过剩余的格数游戏直接结束。

#include <cstdio>
    #include <cstring>
    
    double dp[100010];
    int path[100010];
    
    int main()
    {
    	int n,m;
    	while (scanf("%d%d",&n,&m),n||m)
    	{
    		int i,a,b;
    		memset(dp,0,sizeof(dp));
    		memset(path,-1,sizeof(path));
    		for (i=0;i<m;i++)
    		{
    			scanf("%d%d",&a,&b);
    			path[a]=b;
    		}
    		for (i=n-1;i>=0;i--)
    		{
    			if (path[i]!=-1) 
    				dp[i]=dp[path[i]];
    			else
    			{
    				for (int j=1;j<=6;j++)
    					if (i+j<=n)
    						dp[i]+=dp[i+j]/6;
                        else break;
    				dp[i]+=1.0;
    			}
    		}
    		printf("%.4lf\n",dp[0]);
    	}
    }