首页 > ACM题库 > HDU-杭电 > HDU 4504-威威猫系列故事――篮球梦-动态规划-[解题报告]HOJ
2015
07-17

HDU 4504-威威猫系列故事――篮球梦-动态规划-[解题报告]HOJ

威威猫系列故事――篮球梦

问题描述 :

  威威猫十分迷恋篮球比赛,是忠实的NBA球迷,他常常幻想自己那肥硕的身躯也能飞起扣篮。另外,他对篮球教练工作也情有独钟,特别是对比赛的战术,投篮选择方面也是很有研究,下面就是威威猫研究过的一个问题:
  一场NBA篮球比赛总共48分钟,假如我们现在已经知道当前比分 A:B,A代表我方的比分,B代表对方的比分,现在比赛还剩下t秒时间。我们简单的认为双方各自进攻一次的时间皆固定为15秒(不到15秒则进攻不得分),且为交替进攻,即我方进攻一次,接着对方进攻,依次循环。
  进攻有三种选择方式:(这里不考虑命中率)
  1、造犯规,(假设都两罚一中)得1分;
  2、中距离投篮 得2分;
  3、三分球 得3分。
  为了简化问题,假设在对方回合,由于我方防守比较好,只让对手得1分,且为固定,即对方的进攻回合就为每回合得1分。现在比赛进入最后关头,接下来第一个回合是我方进攻,现在威威猫想要知道教练有多少种不同的选择能使我方可能赢得比赛(可能的意思就是不考虑命中率的情况)。

输入:

输入有多组数据(不超过250组);
每组数据包含3个整数A,B和t,其中A和B 表示当前的比分(0 <= A, B <= 200),t表示还剩多少时间(单位秒 0 <= t <= 600)。

输出:

输入有多组数据(不超过250组);
每组数据包含3个整数A,B和t,其中A和B 表示当前的比分(0 <= A, B <= 200),t表示还剩多少时间(单位秒 0 <= t <= 600)。

样例输入:

88 90 50

样例输出:

6

Hint
样例解析: 当前比分是88:90,还剩50秒则对方还最多有一次进攻机会(最后5秒进攻不成功),我方有两次,对方的最终得分将是91, 我方至少在两回合中拿到4分才能胜利,所以所有方案数是6种,即: 第一球 第二球 1 3 2 2 2 3 3 1 3 2 3 3

关于这题。。我调了半天,告诉WA的人一声,把long long 换成__int64吧,包你过。。。

状态转移为

//d[i][j]表示前i回合获得j分的方法数

d[i][j]=d[i-1][j-1]+d[i-1][j-2]+d[i-1][j-3]

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
__int64 d[100][300];
//d[i][j]表示前i回合获得j分的方法数
//d[i][j]=d[i-1][j-1]+d[i-1][j-2]+d[i-1][j-3]
int main()
{
    __int64 A,B,t;
    while(scanf("%I64d%I64d%I64d",&A,&B,&t)!=-1)
    {
        t/=15;
        B+=t/2;
        t=(t+1)/2;
        d[0][0]=1;
        for(__int64 j=1;j<=3*t;j++)
        {
            d[0][j]=0;
        }
        for(__int64 i=1;i<=t;i++)
        {
            d[i][0]=0;
            d[i][1]=d[i-1][0];
            d[i][2]=d[i-1][0]+d[i-1][1];
            for(__int64 j=3;j<=3*t;j++)
            {
                d[i][j]=d[i-1][j-1]+d[i-1][j-2]+d[i-1][j-3];
            }
        }
        __int64 ans=0;
        __int64 j=B-A+1;
        if(j<0)
        {
            j=0;
        }
        for(;j<=3*t;j++)
        {
            ans+=d[t][j];
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

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

参考:http://blog.csdn.net/zhangwei1120112119/article/details/8707548