Mountain Number （数位dp）

Mountain Number （数位dp）

One integer number x is called "Mountain Number" if:

(1) x>0 and x is an integer;

(2) Assume x=a[0]a[1]...a[len-2]a[len-1](0≤a[i]≤9, a[0] is positive). Any a[2i+1] is larger or equal to a[2i] and a[2i+2](if exists).

For example, 111, 132, 893, 7 are "Mountain Number" while 123, 10, 76889 are not "Mountain Number".

Now you are given L and R, how many "Mountain Number" can be found between L and R (inclusive) ?

Input

The first line of the input contains an integer T (T≤100), indicating the number of test cases.

Then T cases, for any case, only two integers L and R (1≤L≤R≤1,000,000,000).

Output

For each test case, output the number of "Mountain Number" between L and R in a single line.

Sample Input

3

1 10

1 100

1 1000

Sample Output

9

54

384

题目大概：

找出像山一样的数的个数，即偶数位比奇数位大的数，找出范围内这种数的个数。

思路：

基础数位dp，一要注意前导零，二要分好类，讨论位数的大小。

代码：

#include #include #include using namespace std;long long a[22];long long dp[22][25][2];long long dpp(int pos,int qian,int jo,int lead,int limit){ if(pos==-1)return 1; if(!limit&&dp[pos][qian][jo]!=-1)return dp[pos][qian][jo]; long long sun=0; int end=limit?a[pos]:9; for(int i=0;i<=end;i++) { if(!(lead||i)) sun+=dpp(pos-1,9,0,0,limit&&i==a[pos]); else if(jo&&i>=qian) sun+=dpp(pos-1,i,!jo,1,limit&&i==a[pos]); else if(!jo&&i<=qian) sun+=dpp(pos-1,i,!jo,1,limit&&i==a[pos]); } if(!limit)dp[pos][qian][jo]=sun; return sun;}long long go(long long x){ int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dpp(pos-1,9,0,0,1);}int main(){ long long n,m,t; memset(dp,-1,sizeof(dp)); scanf("%I64d",&t); while(t--) { scanf("%I64d%I64d",&n,&m); printf("%I64d\n",go(m)-go(n-1)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。