![hdu 2451 Simple Addition Expression(数位DP )成败在于细节 hdu 2451 Simple Addition Expression(数位DP )成败在于细节](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
亚洲区域赛的题,简单的数位DP题,注重细节。
任何细节都有可能导致wa,所以没有绝对的水题。
把握好细节,此题便A。
#include<stdio.h>
__int64 getans(__int64 s)
{
__int64 ans=0,tmp=1000000000;//这里最大只能取10^9,取10^10就ce了
if(s==0)return 0;//0单独考虑
while(s<tmp)
tmp/=10;
while(s)
{
__int64 p=s/tmp,num;
if(p>=4)//不是最后一位可以取0,1,2,3四个值,之前只考虑了0,1,2三个值,好伤。。。。。
{
num=1;
while(s)
{
num*=4;
s/=10;
}
ans+=num/4*3;//最后一位只能取0,1,2,
}
else
{
__int64 h=s;
num=p;
h/=10;
if(h==0)//最后一位
ans+=num;
else//不是最后一位
{
while(h)
{
num*=4;
h/=10;
}
ans+=num/4*3;
}
}
s%=tmp;
tmp/=10;
}
return ans;
}
int main()
{
__int64 n;
while(scanf("%I64d",&n)!=-1)
printf("%I64d\n",getans(n));
return 0;
}