学步园

题意：NBA比赛，双方共N次进球(N<=100000)，无论哪方，进一个球（得分只可能为1，2，3），就记录一次（记两队分数差的绝对值），问最后两队的比分有多少种。

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

——>>知道最后的比分差k，怎么求得比分呢？设分数较低的一方的最后分数为x，则另一方的最后分数为x + k，设双方最后总分和为S，则x  = (S - k) / 2，可得双方的比分。。所以，只要知道最后双方的总分和，就可以确定双方比分。。于是，问题转化成求最后双方总分和有多少种。

知道了双分总分和，可以求出x : x + k，还有x + k : x，因此，如果x != x +k 即 k ! = 0时，最后结果应乘2。。

状态：dp[i]表示前 i 次进球后双方总分和的种数

状态转移方程：dp[i] = dp[i - 1] + 1（当(diff[i] == 1 && diff[i - 1] == 2) || (diff[i] == 2 && diff[i - 1] == 1) 时）

边界：dp[0] = 1, diff[0] = 0

注：上一次比分差为2，现要达比分差为1，则败者进1分或者进3分，此时可产生2种总分和。。上一次比分差为1，当前比分差为2同理。。

提交G++使用abs(int)会CE（查了一下MinGW里面的cmath，abs确实没有提供 int 参数），C++不会（翻了下MSDN，提供的参数是有 int 的）。。一直对整数求绝对值用abs，用浮点数求绝对值用fabs的我，好囧。。

#include <cstdio>
#include <cmath>

using std::abs;

int main()
{
    int T, N, diff, kase = 0;

    scanf("%d", &T);
    while (T--)
    {
        int dp = 1, last = 0;
        bool ok = true;
        scanf("%d", &N);
        while (N--)
        {
            scanf("%d", &diff);
            if (!ok) continue;
            if (abs(diff - last) > 3 || (diff == last && diff != 1))
            {
                ok = false;
            }
            else
            {
                if ((diff == 2 && last == 1) || (diff == 1 && last == 2))
                {
                    dp++;
                }
                last = diff;
            }
        }
        if (diff != 0)
        {
            dp <<= 1;
        }
        printf("Case #%d: ", ++kase);
        ok ? printf("%d\n", dp) : puts("0");
    }

    return 0;
}