[數位dp] hdu 2451 Simple Addition Expression

[數位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