题目地址：
两份代码，解释在第二份代码里面
第一份代码整理一下看着爽
1 #include2 #include 3 #include 4 using namespace std; 5 long long dp[20][11][3]; 6 int digit[20]; 7 int dfs(int len , int fore , int state , bool limit) 8 { 9 if (len == 0)10 return 1;11 if ( !limit && dp[len][fore][state] != -1 )12 return dp[len][fore][state];13 int res = 0;14 int limitD = limit ? digit[len] : 9 ;15 for (int j = 0 ; j<=limitD; j++)16 {17 int i;18 if (fore == 10 && j == 0) i = 10;19 else i = j;20 if ( state == 0 ){21 if ( fore == 10 || i == fore )22 res += dfs( len - 1 , i , 0 , limit && i == limitD );23 }24 else if ( state == 1 ){25 if ( fore == 10 || i <= fore )26 res += dfs( len - 1 , i , 1 , limit && i == limitD );27 }28 else{29 if ( fore == 10 || i >= fore )30 res += dfs( len - 1 , i , 2 , limit && i == limitD );31 }32 }33 if (!limit)34 dp[len][fore][state] = res;35 return res;36 }37 long long solve(long long x)38 {39 int cnt = 0;40 while (x)41 {42 digit[ ++cnt ] = ( int )( x % 10LL );43 x /= 10LL;44 }45 return dfs( cnt , 10 , 1 , true ) + dfs( cnt , 10 , 2 , true ) - dfs( cnt , 10 , 0 , true );46 }47 int main()48 {49 memset(dp,-1,sizeof dp);50 int N;51 scanf("%d", &N );52 long long a,b;53 while (N--)54 {55 scanf("%lld %lld" , &a , &b );56 printf("%lld\n", solve( b ) - solve ( a - 1LL ) );57 }58 }
1 #include2 #include 3 #include 4 using namespace std; 5 //dp[i][j][k] 长度为i,前一位j,状态为k 6 //k=0 相等 k=1 递增 k=2 递减 7 long long dp[20][11][3]; 8 int digit[20]; 9 //dfs计算在digit限制下，长度为len，前一位为fore，的state状态的数字，特别的令fore==10代表前面全是010 int dfs(int len , int fore , int state , bool limit)11 {12 //最边界计数，即枚举到最后一位，0即为全是前导0。13 if (len == 0)14 {15 return 1;16 }17 //记忆化搜索18 if (!limit && dp[len][fore][state] != -1)19 return dp[len][fore][state];20 int res = 0;21 int limitD = limit?digit[len]:9;22 for (int j = 0 ; j<=limitD; j++)23 {24 int i;25 //确定填写的0,前导0变10,真0还是026 if (fore == 10 && j == 0) i = 10;27 else i = j;28 //如果前导0或者满足要求，那么继续dfs29 //其中有些判断可以省略，但是所有的都加上fore==10,便于理解30 if (state==0) //相等31 {32 if (fore==10||i==fore)33 res += dfs(len-1,i,0,limit&&i==limitD);34 }35 else if (state==1)//递减36 {37 if (fore==10||i<=fore)38 res += dfs(len-1,i,1,limit&&i==limitD);39 }40 else //递增41 {42 if (fore==10||i>=fore)43 res += dfs(len-1,i,2,limit&&i==limitD);44 }45 }46 if (!limit) dp[len][fore][state] = res;47 return res;48 }49 long long solve(long long x)50 {51 int cnt = 0;52 while (x)53 {54 digit[++cnt] = (int)(x % 10LL);55 x /= 10LL;56 }57 //递增+递减-相等58 return dfs(cnt,10,1,true) + dfs(cnt,10,2,true) - dfs(cnt,10,0,true);59 }60 int main()61 {62 memset(dp,-1,sizeof dp);63 int N;64 scanf("%d",&N);65 long long a,b;66 while (N--)67 {68 scanf("%lld%lld",&a,&b);69 printf("%lld\n",solve(b) - solve(a-1LL) );70 }71 }