1 /*
2 题意：把N个数分成两组，一组加起来是A，一组加起来是B，1<=A,B<=9，也可以全分到同一组。其中加是按照他给的规则加，就是一位一位加，超过一位数了再拆分成一位一位加。
3 DP：dp[i][j]记录前i个数累加和为j的方案数，那么状态转移方程：dp[i][j+a[i]] += dp[i-1][j]; 当然，dp[i][a[i]] = 1;
4 然后考虑几种特殊情况：都前往S1门或S2门，方案数+1。另外，比赛时我写出正确的转移方程，结果答案输出dp[n][s1]+dp[n][s2]将近是2倍，没多想，弃之，当时思绪很乱，以为方法错误。。。。
5 */
6 /************************************************
7 * Author :Running_Time
8 * Created Time :2015-8-13 14:39:58
9 * File Name :J.cpp
10 ************************************************/
11
12 #include <cstdio>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <cstring>
17 #include <cmath>
18 #include <string>
19 #include <vector>
20 #include <queue>
21 #include <deque>
22 #include <stack>
23 #include <list>
24 #include <map>
25 #include <set>
26 #include <bitset>
27 #include <cstdlib>
28 #include <ctime>
29 using namespace std;
30
31 #define lson l, mid, rt << 1
32 #define rson mid + 1, r, rt << 1 | 1
33 typedef long long ll;
34 const int MAXN = 1e5 + 10;
35 const int INF = 0x3f3f3f3f;
36 const int MOD = 258280327;
37 int dp[MAXN][10];
38 int a[MAXN];
39 int n, s1, s2;
40
41 int cal(int x, int y) {
42 int ret = x + y;
43 ret %= 9;
44 if (ret == 0) return 9;
45 else return ret;
46 }
47
48 int main(void) { //HDOJ 5389 Zero Escape
49 int T; scanf ("%d", &T);
50 while (T--) {
51 scanf ("%d%d%d", &n, &s1, &s2);
52 int sum = 0;
53 for (int i=1; i<=n; ++i) { //把N个数全加起来再按照规则处理和两个两个加是一样的
54 scanf ("%d", &a[i]); sum = cal (sum, a[i]);
55 }
56
57 memset (dp, 0, sizeof (dp));
58 for (int i=1; i<=n; ++i) {
59 dp[i][a[i]] = 1;
60 for (int j=9; j>=0; --j) {
61 dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
62 if (j + a[i] > 9) {
63 int x = cal (j, a[i]);
64 dp[i][x] = (dp[i][x] + dp[i-1][j]) % MOD;
65 }
66 else {
67 dp[i][j+a[i]] = (dp[i][j+a[i]] + dp[i-1][j]) % MOD;
68 }
69 }
70 }
71
72 int ans = 0;
73 if (cal (s1, s2) == sum) { //两个门都能进去且条件符合
74 ans += dp[n][s1];
75 if (s1 == sum) ans--;
76 }
77 if (s1 == sum) ans++; //可以全进一个门
78 if (s2 == sum) ans++;
79
80 printf ("%d
", ans);
81 }
82
83 return 0;
84 }
递推DP HDOJ 5389 Zero Escape
编译人生，运行世界！