【HDOJ】4972 A simple dynamic programming problem

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 int abs(int x) {
 6     return x<0 ? -x:x;
 7 }
 8 
 9 int main() {
10     int t, n;
11     int cur, past;
12     __int64 ans;
13     bool flag;
14     
15     #ifndef ONLINE_JUDGE
16         freopen("data.in", "r", stdin);
17     #endif
18     
19     scanf("%d", &t);
20     for (int i=1; i<=t; ++i) {
21         scanf("%d", &n);
22         flag = true;
23         past = 0;
24         ans = 1;
25         while (n--) {
26             scanf("%d", &cur);
27             if (!flag)
28                 continue;
29             if (abs(cur-past)>3 || (cur==past && cur!=1)) {
30                 flag = false;
31                 continue;
32             }
33             if (past == 0)
34                 ans *= 2;
35             if (cur == 0)
36                 ans /= 2;
37             if ((cur==1 && past==2) || (cur==2 && past==1))
38                 ans += 2;
39             past = cur;
40         }
41         if (!flag)
42             printf("Case #%d: 0\n", i);
43         else
44             printf("Case #%d: %I64d\n", i, ans);
45     }
46 
47     return 0;
48 }