hdu 5179 beautiful number (數位DP考慮前導0)

beautiful number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 902    Accepted Submission(s): 576

Problem Description

Let A=∑ni=1ai∗10n−i(1≤ai≤9)(n is the number of A's digits). We call A as “beautiful number” if and only if a[i]≥a[i+1] when 1≤i<n and a[i] mod a[j]=0 when 1≤i≤n,i<j≤n(Such as 931 is a "beautiful number" while 87 isn't).

Could you tell me the number of “beautiful number” in the interval [L,R](including L and R)?

Input

The fist line contains a single integer T(about 100), indicating the number of cases.

Each test case begins with two integers L,R(1≤L≤R≤109).

Output

For each case, output an integer means the number of “beautiful number”.

Sample Input

2 1 11 999999993 999999999

Sample Output

10 2

題意：

A：a1a2a3a4......an，如果滿足ai>=ai+1，ai%aj==0  (i<j<=n)，則A稱為完美數。

問在[L,R]内有多少這樣的數

解析：

這一題數位條件隻要滿足ai>ai+1 && ai%ai+1==0

因為整除可以傳遞，b是a的因子，c是b的因子，則c是a的因子

limit隻能表示用于是否達到給定數的邊界！！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long int ll;

int a[13];
ll dp[13][13];

ll dfs(int pos,int state,bool limit,bool lead)
{
    ll ans=0;
    if(pos==-1)
    {
        return 1;
    }

    if(!limit/*&&!lead*/&&dp[pos][state]!=-1) return dp[pos][state];

    int up=limit?a[pos]:9;     
    //if(!lead) up=min(up,state);   //這樣錯的原因是limit隻能表示該次枚舉數位有沒有超a[pos]的界限
	                                //例如邊界是55321，當萬位周遊到4，千位周遊到4時，周遊到百位時limit=true，此時up=3(443..)
    for(int i=0;i<=up;i++)          //但此時正确的up=4（444..）,并沒有周遊到邊界
    {
		if(!lead&&i>state) continue; 
        if(!lead&&i==0) continue; 
        if(lead||state%i==0)
        {
            ans+=dfs(pos-1,i,limit&&i==up,lead&&i==0);
        }
    }

    if(!limit/*&&!lead*/) dp[pos][state]=ans;
    return ans;

}


ll solve(ll n)
{
    ll ans=0;
    int pos=0;
    while(n)
    {
        a[pos++]=n%10;
        n=n/10;
    }
    memset(dp,-1,sizeof(dp));
    ans+=dfs(pos-1,0,true,true);
    return ans;
}


int main()
{
    int t;
    ll l,r;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
}