HDU 6148 Valley Numer

发表于 | 分类于 |

怀疑题目名称真的没错？

数位 DP 裸题，但是有很多细节要注意。
实在不行可以手动模拟。

代码： 

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int LEN = 100;
const int mod = 1e9 + 7;
int T;
char d[LEN + 5];
int tot;
long long f[LEN + 5][10][2][2];
long long dfs(int x,int num,int up,int lead,int top)
{
    if(!x)
        return 1;
    if(!top && ~f[x][num][up][lead])
        return f[x][num][up][lead];
    long long ret = 0;
    int bound = top ? d[x] - '0' : 9;
    for(register int i = x > 1 || !lead ? 0 : 1;i <= bound;++i)
    {
        if(up && num > i)
            continue;
        ret = (ret + dfs(x - 1,i,(num < i || (up && num == i)) && !lead,lead && !i,top && i == bound)) % mod;
    }
    if(!top)
        f[x][num][up][lead] = ret;
    return ret;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(f,-1,sizeof f);
        scanf("%s",d + 1);
        tot = strlen(d + 1);
        reverse(d + 1,d + tot + 1);
        printf("%lld\n",dfs(tot,0,0,1,1));
    }
}