FZU2109 Mountain Number——————数位DP

蔚落 2022-02-21 11:23 176阅读 0赞

# [Mountain Number][] #

Accept: 351 Submit: 875  
Time Limit: 1000 mSec Memory 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**  
3  
1 10  
1 100  
1 1000  
**Sample Output**  
9  
54  
384  
**Source**  
“高教社杯”第三届福建省大学生程序设计竞赛

--------------------

数位DP，训练的时候也看出来了这道题是数位DP了，不过当时自己也没有做出来(太菜了)然后补了一下题目顺便学习数位DP  
数位DP，也就是记忆话搜索，在数字上进行DP，比直接数数要快很多的

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<iostream>
    using namespace std;
    typedef long long ll;
    const ll MAXN = 1e6+7;
    ll dp[66][66][6],dight[66];
    
    //长度，上一位的值，第几位(从高位往低位置数，因为题目定义就是这样子的)，限制
    ll dfs(int len, int pre, int id, bool limit)//
    {
        
            if(len==0)       return 1;
            if(!limit&&dp[len][pre][id%2])  return dp[len][pre][id%2];
    
            int cnt = 0,up = (limit?dight[len]:9);
    
            for(int i=0;i<=up;++i)
            {
        
                    if(id==1)
                    {
        
                            if(i==0)        cnt += dfs(len-1,-2, id, limit&&i==up);//前导零的情况，
                            else            cnt += dfs(len-1, i, id+1, limit&&i==up);
                    }
                    if(id%2==0&&i>=pre)     cnt += dfs(len-1, i, id+1, limit&&i==up);//id是偶数的时候，该位置就是数字的奇数位
                    if(id%2&&id!=1&&i<=pre) cnt += dfs(len-1, i, id+1, limit&&i==up);//id是奇数的时候，需要此位置小于上一位
            }
    
            if(!limit)      dp[len][pre][id%2] = cnt;//没有限制的话就可以记忆话了
            return cnt;
    }
    
    ll solve(ll n)
    {
        
            int k = 0;
            while(n)
            {
        
                    dight[++k] = n%10;
                    n /= 10;
            }
            return dfs(k,-2,1,1);
    }
    
    
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
            int t;
            cin>>t;
            while(t--)
            {
        
                    ll a,b;
                    cin>>a>>b;
                    cout<<solve(b) - solve(a-1)<<endl;
            }
            return 0;
    }

[Mountain Number]: http://acm.fzu.edu.cn/problem.php?pid=2109