首页 > ACM题库 > HDU-杭电 > hdu 4249-a famous equation-动态规划-[解题报告]hoj
2015
05-23

hdu 4249-a famous equation-动态规划-[解题报告]hoj

A Famous Equation

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



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
 

呃,动态规划题。

模拟高精度加法,从低位扫到高位。

dp[i][0]表示前i位满足条件且没进位的方法数,dp[i][1]表示前i位满足条件且进1的方法数。

暴力枚举每一位的数字,然后往前递推即可。

代码很难看,还是勉为其难的贴一下吧……orz,主要是前导0那部分处理的太搓了……

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

char str[105];
int a[15];
int b[15];
int c[15];
long long dp[10][2];

int main()
{
    int i,j,n,tag,t,aup,bup,cup,cnt=1,x,y,z,p,q,r;
    while(scanf("%s",str)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        n=strlen(str);
        tag=0;
        aup=bup=cup=0;
        for (i=n-1;i>=0;i--)
        {
            if (str[i]=='=' || str[i]=='+') tag++;
            else
            {
                t=str[i]=='?'?-1:(str[i]-'0');
                if (tag==0) c[cup++]=t;
                if (tag==1) b[bup++]=t;
                if (tag==2) a[aup++]=t;
            }
        }
        if (cup<max(aup,bup))
        {
            printf("Case %d: 0\n",cnt++);
            continue;
        }
        for (i=aup;i<=cup;i++)
        {
            a[i]=0;
        }
        for (i=bup;i<=cup;i++)
        {
            b[i]=0;
        }
        for (i=0;i<cup;i++)
        {
            for (x=0;x<=9;x++)
            {
                if (i==aup-1 && aup!=1 && x==0 && a[i]==-1) continue;
                if (a[i]!=-1 && x>=1) continue;
                for (y=0;y<=9;y++)
                {
                    if (i==bup-1 && bup!=1 && y==0 && b[i]==-1) continue;
                    if (b[i]!=-1 && y>=1) continue;
                    for (z=0;z<=9;z++)
                    {
                        if (i==cup-1 && cup!=1 && z==0 && c[i]==-1) continue;
                        if (c[i]!=-1 && z>=1) continue;
                        p=a[i]==-1?x:a[i];
                        q=b[i]==-1?y:b[i];
                        r=c[i]==-1?z:c[i];
                        if (p+q==r)
                        {
                            if (i==0) dp[i][0]++;
                            else dp[i][0]+=dp[i-1][0];
                        }
                        if (p+q==10+r)
                        {
                            if (i==0) dp[i][1]++;
                            else dp[i][1]+=dp[i-1][0];
                        }
                        if (p+q+1==r && i!=0)
                        {
                            dp[i][0]+=dp[i-1][1];
                        }
                        if (p+q+1==r+10 && i!=0)
                        {
                            dp[i][1]+=dp[i-1][1];
                        }
                    }
                }
            }
         }
        printf("Case %d: %I64d\n",cnt++,dp[cup-1][0]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。