首页 > ACM题库 > HDU-杭电 > HDU 3254-Extraordinary Tug of War-动态规划-[解题报告]HOJ
2014
03-13

HDU 3254-Extraordinary Tug of War-动态规划-[解题报告]HOJ

Extraordinary Tug of War

问题描述 :

Task

In the game of "tug of war", You’re fighting against an extrordinary opponent — you two teams have exactly the same strength! Yes, this is a so-called "Mirror Match".

Imagine an x-axis along the rope, with origin at the initial position of the center of rope (COR). Then, we can APPROXIMATE the movement of the rope as follows:

1. In the approximation, the rope does NOT move continuously. It moves in discrete steps, step length = dt.
2. Every dt unit time, the rope either moves left or right, exactly sqrt(dt) unit length.
3. The movement of the rope in different steps are independent.

When the step length, dt, goes towards zero, the approximation above goes towards the exact movement.

It’s not hard to imagine that, it usually takes too long to move COR far enough from its original position. So the referee decided to adopt a special rule: observe COR in a period of time (t1, t2). If COR keeps in one side during the whole interval, the team on that side wins. If COR had ever returned to its original position during the interval, the game ends with a draw.

The referee wants the length of the observation interval (i.e. t2-t1) be exactly L, and the probability that one of the teams wins (i.e. the game is NOT a draw) be exactly P%, when should he start to observe?

输入:

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains two integers L, P (1 <= L <= 1000; 0 < P < 100), explained above.

输出:

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains two integers L, P (1 <= L <= 1000; 0 < P < 100), explained above.

样例输入:

2
1 50
1 10

样例输出:

Case 1: 1.000
Case 2: 0.025

第一次写,注释挺清晰了。

注意位运算判断就好了。

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

int dp[20][1<<12];
vector<int> s;       //每一行所有可能的状态,即相邻位不全为1
int can[20];        //用来判断牛是否在1的位置上

void debug(int i)
{
    for(int f=0;f<s.size();f++)
    {
        printf("dp[%d][%d]=%d\n",i,f,dp[i][f]);
    }
}
int main()
{
    int n,m,a;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        s.clear();
        memset(dp,0,sizeof(dp));
        memset(can,0,sizeof(can));

        int tmp=1<<m;
        for(int i=0;i<tmp;i++)
        {
            if( (i&(i<<1))==0) s.push_back(i);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a);
                if(!a) can[i]+=(1<<(m-j));             //相当于对每一行的01串取反
            }
        }
        for(int i=0;i<s.size();i++) //计算dp的初始值,即第1行的第i种状态的值
        {
            if((s[i]&can[1])==0)      //can[1]的0位置才能够出现1,can[1]的1位置只能出现0
            {
                dp[1][i]=1;
            }
        }

        for(int i=2;i<=n;i++)           //从第二行开始递推
        {
            for(int j=0;j<s.size();j++) //第i行选择一个状态
            {
                if((s[j]&can[i])==0)
                {
                    for(int k=0;k<s.size();k++) //第i-1行选择一个状态
                    {
                        if( ((s[k]&can[i-1]) ==0)&& ((s[j]&s[k])==0) )  //i行和i-1行的状态没有上下相邻的1
                        {
                            dp[i][j]=(dp[i][j]+dp[i-1][k])%100000000;
                        }
                    }
                }
            }
         //   debug(i);
        }
        int ans=0;
        for(int i=0;i<s.size();i++)
        {
            ans=(ans+dp[n][i])%100000000;
        }
        printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/t1019256391/article/details/9232625


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!