Problem 2109 Mountain NumberAccept: 231Submit: 586
Time Limit: 1000 mSecMemory Limit : 32768 KB
文章图片
Problem Description 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 31 101 1001 1000
文章图片
Sample Output 954384
文章图片
Source “高教社杯”第三届福建省大学生程序设计竞赛
【FZU-2109 Mountain Number(数位dp)】题意:给出区间[L,R],问在这个区间中有多少个特殊数,特殊数的奇数位要不小于相邻的偶数位
题解:数位dp,记录当前到达第i位,前一位的数是pre,当前位是奇数位时要大于pre,当前位是偶数位时要小于pre,还要注意边界情况,如果没有到达边界那么可以用
记忆化搜索剪枝,如果到达边界则要重新搜索,是否到达边界用mark来判断
#include
#include
#include
#include
using namespace std;
typedef long long LL;
int dp[20][20][2];
int mx[20],len;
int dfs(int index,int pre,bool odd,bool mark){
if(index==len) return 1;
//搜索到末尾,表示找到一个结果,返回1
if(!mark&&~dp[index][pre][odd]) return dp[index][pre][odd];
//如果当前每到边界就直接返回已保存过的结果数
int ret=0;
int r=mark?mx[index]:9;
for(int i=0;
i<=r;
i++){
if(odd&&i>=pre) ret+=(dfs(index+1,i,odd^1,mark&&i==r));
else if(!odd&&i<=pre) ret+=(dfs(index+1,i,odd^1,mark&&i==r));
}
if(!mark) dp[index][pre][odd]=ret;
//如果没有到达边界就用dp保存当前位能有多少个结果
return ret;
}int solve(int x){
len=0;
memset(dp,-1,sizeof(dp));
memset(mx,0,sizeof(mx));
while(x){
mx[len++]=x%10;
x/=10;
}
if(len<=1) return mx[0];
reverse(mx,mx+len);
return dfs(0,9,0,1);
}
int main(){
int T,l,r;
scanf("%d",&T);
while(T--){scanf("%d%d",&l,&r);
printf("%d\n",solve(r)-solve(l-1));
}
return 0;
}
