hdu 5389 dp

类似于背包，dp[i]表示选出一些数它们的“根”是i的方法数（包括了所有人的“根”是i的情况）。然后就是要注意所有人都走另一个门的情况。
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int MOD = 258280327;
 7 const int N = 100001;
 8 const int M = 10;
 9 int id[N];
10 int dp[M];
11 int help[M];
12 
13 int main ()
14 {
15     int t;
16     scanf("%d", &t);
17     while ( t-- )
18     {
19         int n, a, b, sum = 0;
20         scanf("%d%d%d", &n, &a, &b);
21         for ( int i = 1; i <= n; i++ )
22         {
23             scanf("%d", id + i);
24             sum += id[i];
25             if ( sum > 9 ) sum -= 9;
26         }
27         int ab = a + b;
28         if ( ab > 9 ) ab -= 9;
29         if ( ab == sum )
30         {
31             memset( dp, 0, sizeof(dp) );
32             for ( int i = 1; i <= n; i++ )
33             {
34                 for ( int j = 1; j < M; j++ )
35                 {
36                     int tmp = j + id[i];
37                     if ( tmp > 9 ) tmp -= 9;
38                     help[tmp] = dp[j];
39                 }
40                 for ( int j = 1; j < M; j++ )
41                 {
42                     int tmp = j + id[i];
43                     if ( tmp > 9 ) tmp -= 9;
44                     dp[tmp] += help[tmp];
45                     if ( dp[tmp] >= MOD ) dp[tmp] -= MOD;
46                 }
47                 dp[id[i]]++;
48                 if ( dp[id[i]] >= MOD ) dp[id[i]] -= MOD;
49             }
50             //所有人都走b门的情况
51             if ( b == sum )
52             {
53                 printf("%d
", ( dp[a] + 1 ) % MOD);
54             }
55             else
56             {
57                 printf("%d
", dp[a]);
58             }
59         }
60         else
61         {
62             if ( sum == a || sum == b )
63             {
64                 if ( a == b ) printf("2
");
65                 else printf("1
");
66             }
67             else
68             {
69                 printf("0
");
70             }
71         }
72     }
73     return 0;
74 }