首页 > 代码库 > HDU 4972 A simple dynamic programming problem（数学思维题）

HDU 4972 A simple dynamic programming problem（数学思维题）

2024-07-18 23:22:14   231人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4972


Problem Description
Dragon is watching NBA. He loves James and Miami Heat.

Here‘s an introduction of basketball game:http://en.wikipedia.org/wiki/Basketball. However the game in Dragon‘s version is much easier:

"There‘s two teams fight for the winner. The only way to gain scores is to throw the basketball into the basket. Each time after throwing into the basket, the score gained by the team is 1, 2 or 3. However due to the uncertain factors in the game, it’s hard to predict which team will get the next goal".

Dragon is a crazy fan of Miami Heat so that after each throw, he will write down the difference between two team‘s score regardless of which team keeping ahead. For example, if Heat‘s score is 15 and the opposite team‘s score is 20, Dragon will write down 5. On the contrary, if Heat has 20 points and the opposite team has 15 points, Dragon will still write down 5.

Several days after the game, Dragon finds out the paper with his record, but he forgets the result of the game. It‘s also fun to look though the differences without knowing who lead the game, for there are so many uncertain! Dragon loves uncertain, and he wants to know how many results could the game has gone?
 

Input
The first line of input contains only one integer T, the number of test cases. Following T blocks, each block describe one test case.

For each test case, the first line contains only one integer N(N<=100000), which means the number of records on the paper. Then there comes a line with N integers (a1, a2, a3, ... , an). ai means the number of i-th record.
 

Output
Each output should occupy one line. Each line should start with "Case #i: ", with i implying the case number. Then for each case just puts an integer, implying the number of result could the game has gone.
 

Sample Input
2
2
2 3
4
1 3 5 7
 

Sample Output
Case #1: 2
Case #2: 2
 

Source
2014 Multi-University Training Contest 10


题意：

        给出一个数组记录了两队之间分差,分差不分是哪一队高哪一队低，（如：A队20分，B队15分和A队15分B队20分，分差都为5），

求最终有多少种比分的可能性。

官方题解：http://blog.sina.com.cn/s/blog_6bddecdc0102v01l.html




代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    int t;
    int n, d[100017];
    int cas = 0;
    scanf("%d",&t);
    while(t--)
    {
        memset(d,0,sizeof(d));
        scanf("%d", &n);
        int cnt = 0;
        int flag = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&d[i]);
        }
        for(int i = 1; i <= n; i++)
        {
            if ((d[i]==d[i-1] && d[i]!=1) || abs(d[i]-d[i - 1])>3)
            {
                //第一次是可以为零的,相邻的分差是不能大于三的，因为每次最多增加三分
                flag = 1;
                break;
            }
            if (d[i]*d[i-1] == 2)//1：2或者2：1
                cnt++ ;
        }
        printf("Case #%d: ",++cas);
        if (flag)
        {
            printf("0\n");
            continue;
        }
        if (d[n] == 0)//最终分差为零
            printf("%d\n",cnt+1);
        else
            printf("%d\n",2*(cnt+1));
    }
    return 0;
}



HDU 4972 A simple dynamic programming problem（数学思维题）


联系
我们