[数位dp] hdu 2451 Simple Addition Expression

题意：给N，求小于N的数中，三个连续的数相加不进位的数有多少个。

思路：和上题类似，就是不是个位的话，可以放0,1,2,3，个位的话只能放0,1,2。

然后就是边界考虑一下，不能超过当前位。

然后就是边界的判断，不是等于len而是等于当前位。

代码：

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
using namespace std;
//2014年9月24日15:50:51
__int64 dp[22];
int num[22];
__int64 dfs(int site,int f)
{
    if(site==0) return 1;
    if(!f&&~dp[site]) return dp[site];
    int len;
    if(site!=1) len=f?min(3,num[site]):3;  //注意上限
    else len=f?min(2,num[site]):2;
    __int64 ans=0;
    for(int i=0;i<=len;i++)
        ans+=dfs(site-1,f&&i==num[site]); //注意边界判定
    if(!f) dp[site]=ans;
    return ans;
}
__int64 solve(__int64 x)
{
    int cnt=0;
    while(x)
    {
        num[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,1);
}
int main()
{
    __int64 x;
    memset(dp,-1,sizeof(dp));
    while(scanf("%I64d",&x)!=-1)
    {
        printf("%I64d\n",solve(x-1));
    }
    return 0;
}
//2014年9月24日16:17:25

[数位dp] hdu 2451 Simple Addition Expression

原文：http://blog.csdn.net/wdcjdtc/article/details/39528541