beautiful number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 919    Accepted Submission(s): 590


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
21 11999999993 999999999
 
Sample Output
102
 

Source
BestCoder Round #31
 

Recommend
hujie

思路:数位DP

思路:都踏马是套路压呀!

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define bug1 cout <<"bug1"<<endl
#define bug2 cout <<"bug2"<<endl
#define bug3 cout <<"bug3"<<endl
using namespace std;
typedef long long ll;


const int MAX_N=2e5+5;
int dp[30][10];
int a[30];
int n,m;
int len;

int dfs(int pos,int pre,bool lead,bool limit){///最高位,前一位,前导零,是否限制
    if(pos==-1) return 1;
    if(!limit && !lead && dp[pos][pre]!=-1) return dp[pos][pre];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        if(pos==len)    ans+=dfs(pos-1,i,i==0&&lead,limit&&a[pos]==i);
        else{
            if(pre==0){
                ans+=dfs(pos-1,i,i==0&&lead,limit&&a[pos]==i);
            }
            else{
                if(i==0)    continue;
                if(i<=pre && pre%i==0)   ans+=dfs(pos-1,i,i==0&&lead,limit&&a[pos]==i);
            }
        }
    }
    if(!limit && !lead) dp[pos][pre]=ans;
    return ans;
}

int solve(int t){
    int pos=0;
    while(t){
        a[pos++]=t%10;
        t/=10;
    }
    len=pos-1;
    return dfs(pos-1,0,true,true);
    ///最高位,前一位,前导零,是否限制
}

int main(void){
    int T;
    cin >> T;
    while(T--){
        scanf("%d%d",&n,&m);
        memset(dp,-1,sizeof(dp));
        printf("%d\n",solve(m)-solve(n-1));
    }
}