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

题面：

Zero Escape

4
3 9 1
1 2 6
3 9 1
2 3 3
5 2 3
1 1 1 1 1
9 9 9
1 2 3 4 5 6 7 8 9

1
0
10
60

    开始没想到递推，队友说了下dp，往这方面想了下就想到了。状态转移方程为dp[i][j]=(dp[i-1][tmp]+dp[i-1][j])%mod;其中tmp为j-arr[i]，i是当前下标，j从1到9，若算出的tmp小于等于0还需加上9。dp[i][j]的含义是到第i位为止，前i个数中的若干个加起来和为j的方案数，转移方程中的两项分别对应，当前i位取或不取。因为每个数字是由确定的两个数字组合加起来得到的，比如2，若其中一个为1，那么另外一个也一定为1。且存在这样的性质，若干个数，按给定的规则先加，或者分开加，再组合在一起，得到的结果是一样的。故可以先预先把所有的数加起来，若其和和a+b得到的结果相同，那么直接取dp[n][a]+dp[n][b]的值即可，若不同，那么只可以放在任意门中，分别检查一下即可。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#define mod 258280327
using namespace std;
int dp[100010][10],arr[100010];
//按给定规则转化为个位数
int modify(int x)
{
    int res=0;
    while(x)
    {
        res+=(x%10);
        x/=10;
    }
    if(res>9)
        return modify(res);
    else
        return res;
}
int main()
{
    int t,n,a,b,tmp,ans;
    int sum,xx;
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
		//初始化
        memset(dp,0,sizeof(dp));
        scanf("%d%d%d",&n,&a,&b);
		//读入
        for(int i=1;i<=n;i++)
            scanf("%d",&arr[i]);
        for(int i=1;i<=n;i++)
        {
			//并同时转化为对应的个位数
            arr[i]=modify(arr[i]);
            sum+=arr[i];
        }
        sum=modify(sum);
        xx=a+b;
        xx=modify(xx);
		//看是否相等
        if(sum==xx)
        {
          dp[1][arr[1]]=1;
          for(int i=2;i<=n;i++)
          {
              for(int j=1;j<=9;j++)
              {
                  tmp=j-arr[i];
                  if(tmp<=0)
                     tmp+=9;
				  //当前位分别取1-9，由前面对应的关系推过来
                  dp[i][j]=(dp[i-1][tmp]+dp[i-1][j])%mod;
              }
          }
        printf("%d\n",(dp[n][a]+dp[n][b])%mod);
       }
		//不相等，只可能单独在一扇门中
       else
       {
           ans=0;
           if(sum==a)
              ans++;
           if(sum==b)
               ans++;
           printf("%d\n",ans);
       }
    }
    return 0;
}

HDU 5389 Zero Escape（dp解法）

原文：http://blog.csdn.net/david_jett/article/details/47617099