HDU 6148 Valley Number

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll MOD=1e9+7;
 5 ll dim[105];
 6 ll dp[105][2][10];
 7 ll dfs(int x,int up,int st,int jb,int fz){
 8     if (!x) {
 9         return 1;
10     }
11     if (!jb && !fz && dp[x][up][st]!=-1 && up!=-1 && st!=-1) return dp[x][up][st];
12     ll ret=0;
13     int maxn=9;
14     if (jb) maxn=dim[x];
15     for (int i=0; i<=maxn; i++){
16         if (fz){
17             if (i==0) ret=(ret+dfs(x-1,-1,-1,(jb==1 && maxn==i),1))%MOD;
18             else ret=(ret+dfs(x-1,-1,i,(jb==1 && maxn==i),0))%MOD;
19         }
20         else {
21             if (up==1 && i<st) continue;
22             if (i>st) ret=(ret+dfs(x-1,1,i,(jb==1 && maxn==i),0))%MOD;
23             else if (i==st) ret=(ret+dfs(x-1,up,st,(jb==1 && maxn==i),0))%MOD;
24             else ret=(ret+dfs(x-1,0,i,(jb==1 && maxn==i),0))%MOD;
25         }
26     }   
27     if (!jb && !fz && up!=-1 && st!=-1) return dp[x][up][st]=ret;
28     return ret;
29 }
30 int main(){
31     memset(dp,-1,sizeof(dp));
32     int T;
33     scanf("%d",&T);
34     while (T--){
35         string a;
36         cin>>a;
37         for (int i=0; i<a.length(); i++)
38             dim[a.length()-i]=a[i]-‘0‘;
39         printf("%lld\n",(dfs(a.length(),-1,-1,1,1)-1+MOD)%MOD);
40     }
41 }