[原创]FZU 2109 Mountain Number [数位DP]【动态规划】

2016-08-31 15:57:33 Tabris_ 阅读数：227

博客爬取于2020-06-14 22:43:34
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52385951

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2109
--------------------------------.
Problem 2109 Mountain Number
Accept: 231 Submit: 592
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

“高教社杯”第三届福建省大学生程序设计竞赛

---------------------------------------------------------------.
题目大意:
就是给你一个区间[l,r]
问你在这个区间内满足从高位起偶数位的数字要**>=**两边的数字 这样的有多少个

解题思路:
标准的数位DP
dp[第多少位][上一位的数字][奇数位or偶数位];
开这样一个数组 然后DP就行了
我用的记忆华搜索
dfs(int pos,int weishu,int pre,int limit)
dfs(第多少位,位数,上一位的数字,限制)；

决策的时候

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0; i<=endi; i++)
{
    if(weishu==1) //表示前面还是只有前导0
        if(i==0)    res+=dfs(pos-1,weishu  ,9,limit&&(i==endi));
        else        res+=dfs(pos-1,weishu+1,i,limit&&(i==endi));

    if(weishu%2==1&&weishu!=1)//奇数位
        if(pre>=i)  res+=dfs(pos-1,weishu+1,i,limit&&(i==endi));

    if(weishu%2==0)  //偶数位
        if(pre<=i)  res+=dfs(pos-1,weishu+1,i,limit&&(i==endi));
}

如果觉得还是wrong的注意下输出是%lld 还是%I64d
%lld 就会返回wrong answer
还有就是FZU不支持 #include < bits/stdc++.h>

附本题代码
------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# include <iostream>
# include <stdio.h>
# include <string.h>
using namespace std;

typedef long long LL;
const int MOD  = 1e9+7;
const int maxn = 200010;

int num[70],len;
LL  dp[50][12][5];

LL dfs(int pos,int weishu,int pre,int limit)
{
    if(pos < 0)    return 1;

    if(dp[pos][pre][weishu%2]!=-1&&!limit)
        return dp[pos][pre][weishu%2];

    int endi = 9;
    if(limit) endi = num[pos];

    LL res = 0;
    for(int i=0; i<=endi; i++)
    {
        if(weishu==1)
            if(i==0)    res+=dfs(pos-1,weishu  ,9,limit&&(i==endi));
            else        res+=dfs(pos-1,weishu+1,i,limit&&(i==endi));

        if(weishu%2==1&&weishu!=1)
            if(pre>=i)  res+=dfs(pos-1,weishu+1,i,limit&&(i==endi));

        if(weishu%2==0)
            if(pre<=i)  res+=dfs(pos-1,weishu+1,i,limit&&(i==endi));
    }

    if(!limit) dp[pos][pre][weishu%2] = res;
    return res;
}

LL solve(LL n)
{
    len = 0;

    while(n)
    {
        num[len++] = n%10;
        n /= 10;
    }

    return dfs(len-1,1,9,1);
}

int main()
{
    memset(dp,-1,sizeof(dp));

    int _,p=0;
    scanf("%d",&_);
    while(_--)
    {
        LL n,m;
        scanf("%I64d%I64d",&m,&n);
       // printf("%lld %lld\n",solve(n),solve(m-1));
        printf("%I64d\n",solve(n)-solve(m-1));
    }
    return 0;
}