HDOJ 4249 A Famous Equation DP

DP:

DP[len][k][i][j] 再第len位，第一個數len位為i，第二個數len位為j，和的第len位為k

每一位可以從後面一位轉移過來，可以進位也可以不進位

A Famous Equation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 500 Accepted Submission(s): 147


Problem Description Mr. B writes an addition equation such as 123+321=444 on the blackboard after class. Mr. G removes some of the digits and makes it look like “1?3+??1=44?”. Here “?” denotes removed digits. After Mr. B realizes some digits are missing, he wants to recover them. Unfortunately, there may be more than one way to complete the equation. For example “1?3+??1=44?” can be completed to “123+321=444” , “143+301=444” and many other possible solutions. Your job is to determine the number of different possible solutions.
Input Each test case describes a single line with an equation like a+b=c which contains exactly one plus sign “+” and one equal sign “=” with some question mark “?” represent missing digits. You may assume a, b and c are non-negative integers, and the length of each number is no more than 9. In the other words, the equation will contain three integers less than 1,000,000,000.
Output For each test case, display a single line with its case number and the number of possible solutions to recover the equation.
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.
 

Source Fudan Local Programming Contest 2012

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long int LL;

char cpp[200];
int a[200],len1,b[200],len2,c[200],len3;
LL dp[20][20][20][20];

int main()
{
    int cas=1;
    while(cin>>cpp)
    {
        len1=len2=len3=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        int n=strlen(cpp);
        int i; stack stk;
        for(i=0;i0;i--) if(a[i]==0) len1--; else break;
        for(int i=len2-1;i>0;i--) if(b[i]==0) len2--; else break;
        for(int i=len3-1;i>0;i--) if(c[i]==0) len3--; else break;

        memset(dp,0,sizeof(dp));

        ///len==0
        for(int i=0;i<=9;i++)
        {
            if(a[0]==-1||a[0]==i)
            for(int j=0;j<=9;j++)
            {
                if(b[0]==-1||b[0]==j)
                for(int k=0;k<=9;k++)
                if(c[0]==-1||c[0]==k)
                {
                    if(k==(i+j)%10)
                        dp[0][k][i][j]=1;
                }
            }
        }
        ///len=1...
        for(int len=1;len=len1&&i!=0) continue;
                if(a[len]==-1||a[len]==i)
                for(int j=0;j<=9;j++)
                {
                    if(len==len2-1&&j==0) continue;
                    if(len>=len2&&j!=0) continue;
                    if(b[len]==-1||b[len]==j)
                    for(int k=0;k<=9;k++)
                    {
                        if(len==len3-1&&k==0) continue;
                        if(((i+j)%10!=k)&&((i+j+1)%10!=k))
                                continue;
                        if(c[len]==-1||c[len]==k)
                        {
                            ///沒有進位
                            if((i+j)%10==k)
                            {
                                for(int ii=0;ii<=9;ii++)
                                    for(int jj=0;jj<=9;jj++)
                                        for(int kk=0;kk<=9;kk++)
                                        {
                                            if((ii+jj==kk)||(ii+jj+1==kk))
                                                dp[len][k][i][j]+=dp[len-1][kk][ii][jj];
                                        }
                            }
                            ///有進位
                            if((i+j+1)%10==k)
                            {
                                 for(int ii=0;ii<=9;ii++)
                                    for(int jj=0;jj<=9;jj++)
                                        for(int kk=0;kk<=9;kk++)
                                        {
                                            if(((ii+jj>=10)&&(ii+jj)%10==kk)||((ii+jj+1>=10)&&(ii+jj+1)%10==kk))
                                                dp[len][k][i][j]+=dp[len-1][kk][ii][jj];
                                        }
                            }
                        }
                    }
                }
            }
        }
        LL ans=0;
        int mx=max(len1,max(len2,len3));
        for(int i=0;i<=9;i++)
            for(int j=0;j<=9;j++)
                for(int k=0;k<=9;k++)
                    if((i+j==k)||(i+j+1==k))
                    {
                        if(mx==1&&i+j!=k) continue;
                        ans+=dp[mx-1][k][i][j];
                    }
        cout<<"Case "<