pid=4972" target="_blank" style="">题目链接：hdu 4972 A simple dynamic programming problem

题目大意：两支球队进行篮球比赛，每进一次球后更新比分牌，比分牌的计数方法是记录两队比分差的绝对值，每次进球的分可能是1，2，3分。

给定比赛中的计分情况。问说最后比分有多少种情况。

解题思路：分类讨论：

• 相邻计分为1-2或者2-1的时候，会相应有两种的的分情况
• 相邻计分之差大于3或者说相等而且不等于1的话，为非法输入
• 其它情况下。不会造成新的比分情况产生
• 对于最后一次比分差为0的情况，就没有谁赢谁输一说。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e5+5;

int N, a[maxn];

int solve () {

    int cnt = 1;

    for (int i = 1; i <= N; i++) {

        if (a[i] == 1 && a[i-1] == 2)

            cnt++;

        else if (a[i] == 2 && a[i-1] == 1)

            cnt++;

        else if (a[i] - a[i-1] > 3 || a[i-1] - a[i] > 3)

            return 0;

        else if (a[i] == a[i-1] && a[i] != 1)

            return 0;

    }

    if (a[N] == 0)

        return cnt;

    else

        return cnt * 2;

}

int main () {

    int cas;

    scanf("%d", &cas);

    for (int kcas = 1; kcas <= cas; kcas++) {

        scanf("%d", &N);

        for (int i = 1; i <= N; i++)

            scanf("%d", &a[i]);

        printf("Case #%d: %d\n", kcas, solve());

    }

    return 0;

}