题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4249
题目大意：给一个a+b=c的表达式，但是a、b、c中部分位的数字丢失，并用？代替，问有多少种方案使得这个表达式成立。
Sample Input
7+1?=1?
?1+?1=22
Sample Output
Case 1: 3
Case 2: 1
Hint
There are three solutions for the first case: 7+10=17, 7+11=18, 7+12=19 There is only one solution for the second case: 11+11=22 Note that 01+21=22 is not a valid solution because extra leading zeros are not allowed.
分析：网上的代码有2种，第一种：
状态dp[len][i][j][k]表示三个数a，b，c的len位上的三个数字i , j, k 。
if((i+j)%10==k) //上一位不进1
dp[len][i][j][k]+=dp[len-1][ii][jj][kk];其中ii+jj==kk||ii+jj+1==kk
if((i+j+1)%10==k) //上一位进1
dp[len][i][j][k]+=dp[len-1][ii][jj][kk];
其中ii+jj>=10&&(ii+jj)%10==kk,ii+jj+1>=0,(ii+jj+1)%10==kk
最后答案是sum(dp[len-1][i][j][k]), (i+j==k||i+j+1==k)
代码如下：
# include<iostream>
# include<cstring>
# include<cstdio>
# include<stack>
# include<algorithm>
# define LL __int64 //如果需要改成long long 的话多么方便
using namespace std; int len1,len2,len3,a[],b[],c[];
LL dp[][][][];
stack<char >st;
LL DP()
{
int i,j,k,l;
memset(dp,,sizeof(dp));
for(i=; i<; i++)
{
if(a[] != - && a[] != i) //枚举该位，如果不是？则必须是给定的数字i,不能枚举其他数
continue;
for(j=; j<; j++)
{
if(b[] != - && b[] != j)
continue;
for(k=; k<; k++)
{
if(c[] != - && c[] != k)
continue;
if((i+j)%==k)
dp[][i][j][k] = ;
}
}
}
for(l=; l<len3; l++) //从和的倒数第2位开始枚举
{
for(i=; i<; i++)
{
if(a[l] != - && a[l] != i)
continue;
if(l==len1- && i==) //首位不能是0
continue;
if(l>=len1 && i!=) //和比加数多余的位，相当于在加数的前面加0
continue;
for(j=; j<; j++)
{
if(b[l] !=- && b[l] !=j)
continue;
if(l==len2- && j==)
continue;
if(l>=len2 && j!=)
continue;
for(k=; k<; k++)
{
if(c[l] != - && c[l] !=k)
continue;
if(l==len3- && k==)
continue;
if((i+j)% !=k &&(i+j+)%!=k) //因为对应位上的三个数字a+b=c或者a+b+1=c;是从前往后进位的
continue;
if((i+j)%==k) //上一位不进1
{
for(int ii=; ii<; ii++)
for(int jj=; jj<; jj++)
for(int kk=; kk<; kk++)
{
if(dp[l-][ii][jj][kk] != &&(ii+jj==kk||ii+jj+==kk))
dp[l][i][j][k] += dp[l-][ii][jj][kk];
}
}
if((i+j+)%==k) //上一位进1
{
for(int ii=; ii<; ii++)ii+jj
for(int jj=; jj<; jj++)
for(int kk=; kk<; kk++)
{
if(dp[l-][ii][jj][kk] != &&(((ii+jj>= && (ii+jj)%==kk))||(ii+jj+>= &&(ii+jj+)%==kk)))
dp[l][i][j][k] += dp[l-][ii][jj][kk];
}
}
}
}
}
}
LL ans = ;
for(i=; i< ; i++)
for(j=; j<; j++)
for(k=; k<; k++)
{
if(dp[len3-][i][j][k] != && (i+j==k || i+j+==k))
ans += dp[len3-][i][j][k];
}
return ans;
}
int main()
{
char s[];
int cas=;
while(~scanf("%s",s))
{
int i,len = strlen(s);
memset(a,,sizeof(a));
memset(b,,sizeof(b));
memset(c,,sizeof(c));
for(i=; s[i]!='+'; i++)
st.push(s[i]);
len1 = ;
while(!st.empty()) //提取第一个加数，逆序存放到a数组里边，这样进位就是从前往后进位
{
if(st.top() != '?')
a[len1++] = st.top()-'';
else a[len1++] = -;
st.pop();
}
for(i++; s[i] != '='; i++)
st.push(s[i]);
len2 = ;
while(!st.empty()) //提取第2个加数
{
if(st.top() != '?')
b[len2++] = st.top() - '';
else b[len2++] = -;
st.pop();
}
for(i++; i<len; i++)
st.push(s[i]);
len3 = ;
while(!st.empty()) //提取第3个加数
{
if(st.top() != '?')
c[len3++] = st.top() - '';
else c[len3++] = -;
st.pop();
}
printf("Case %d: %I64d\n",cas++,DP());
}
return ;
}