递推DP HDOJ 5389 Zero Escape-白红宇

递推DP HDOJ 5389 Zero Escape

阅读量：6657 次

发布时间：2019-06-25

本文共 2043 字，大约阅读时间需要 6 分钟。

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.cpp10  ************************************************/11 12 #include 
     
      13 #include 
      
       14 #include 
       
        15 #include 
        
         16 #include 
         
          17 #include 
          
           18 #include 
           
            19 #include 
            
             20 #include 
             
              21 #include 
              
               22 #include 
               
                23 #include 
                
                 24 #include 
                 25 #include 
                  
                   26 #include 
                   
                    27 #include 
                    
                     28 #include 
                     
                      29 using namespace std;30 31 #define lson l, mid, rt << 132 #define rson mid + 1, r, rt << 1 | 133 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 Escape49 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\n", ans);81 }82 83 return 0;84 }