首页 > 代码库 > HDU-4249-A Famous Equation(DP)
HDU-4249-A Famous Equation(DP)
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: 1HintThere 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
思路：dp[i][0]表示从右往左第i位不进位的方法数，dp[i][1]表示进位的方法数。 坑点：①long long。②前导零。③1+1=2这种情况结果为1，加特判还WA了。④细节。
代码写得太挫，还是贴上来吧。。。
#include<stdio.h>
#include<string.h>
char a[50],b[50],c[50],s[100];
long long dp[10][2];
int main()
{
int la,lb,lc,i,j,k,now,p,q,jp,jq,cas=1;
while(~scanf("%s",s))
{
for(i=0;s[i];i++) if(s[i]=='+' || s[i]=='=') s[i]=' ';
sscanf(s,"%s%s%s",a,b,c);
la=strlen(a)-1;
lb=strlen(b)-1;
lc=strlen(c)-1;
dp[0][0]=1;
dp[0][1]=0;
now=1;
while(la>=0 || lb>=0 || lc>=0)
{
p=q=jp=jq=0;
if(la>=0 && a[la]=='?')
{
for(i=0;i<=9;i++)
{
if(!la && now>1 && !i) continue;
if(lb>=0 && b[lb]=='?')
{
for(j=0;j<=9;j++)
{
if(!lb && now>1 && !j) continue;
if(lc>=0 && c[lc]=='?')
{
for(k=0;k<=9;k++)
{
if(!lc && now>1 && !k) continue;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
else
{
if(lc>=0) k=c[lc]-'0';
else k=0;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
}
else
{
if(lb>=0) j=b[lb]-'0';
else j=0;
if(lc>=0 && c[lc]=='?')
{
for(k=0;k<=9;k++)
{
if(!lc && now>1 && !k) continue;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
else
{
if(lc>=0) k=c[lc]-'0';
else k=0;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
}
}
else
{
if(la>=0) i=a[la]-'0';
else i=0;
if(lb>=0 && b[lb]=='?')
{
for(j=0;j<=9;j++)
{
if(!lb && now>1 && !j) continue;
if(lc>=0 && c[lc]=='?')
{
for(k=0;k<=9;k++)
{
if(!lc && now>1 && !k) continue;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
else
{
if(lc>=0) k=c[lc]-'0';
else k=0;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
}
else
{
if(lb>=0) j=b[lb]-'0';
else j=0;
if(lc>=0 && c[lc]=='?')
{
for(k=0;k<=9;k++)
{
if(!lc && now>1 && !k) continue;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
else
{
if(lc>=0) k=c[lc]-'0';
else k=0;
if(i+j==k) p++;
if(i+j==k-1) jp++;
if(i+j-10==k) q++;
if(i+j-10==k-1) jq++;
}
}
}
dp[now][0]=dp[now-1][0]*p+dp[now-1][1]*jp;
dp[now][1]=dp[now-1][0]*q+dp[now-1][1]*jq;
now++;
la--;
lb--;
lc--;
}
printf("Case %d: %I64d\n",cas++,dp[now-1][0]);
}
}
HDU-4249-A Famous Equation(DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。