HDU6148 Valley Numer {DP}【数位DP】

题解

    查找区间 [ 0 , n ] [0, n] [0,n]内有多少个数字上没有峰值的数字。注意 12221 12221 12221也算有峰值。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define lowbit(x) ((x) & -(x));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5 + 10, NN = 1e3 + 10, INF = 0x3f3f3f3f, LEN = 110;
const ll MOD = 1e9 + 7;
const ull seed = 31;
ll digit[LEN];
ll dp[LEN][10][3];  //三维下标为0表示不确定前面的状态，1表示递减，2表示递增
ll dfs(ll len, bool ismax, ll isup, ll last, bool lead_zero) {
          
   
    // lead_zero表示是否处理到了可以处理的数字，意思就是是否已经抛弃了前导零
    ll ans = 0;
    if (!len)
        return lead_zero ? 1LL : 0LL;
    //若已经抛弃前导零找到可以处理的数字则输出1
    if (!ismax && dp[len][last][isup] != -1)
        return dp[len][last][isup];
    ll maxx = ismax ? digit[len] : 9LL;
    for (ll i = 0; i <= maxx; i++) {
          
   
        if (isup == 2 && i < last)
            continue;
        //若isup已经为2就是之前已经出现递增，若i<last则在递增后又出现了递减，不允许出现这种情况，跳过
        else if (!lead_zero && i == 0)
            ans =
                (ans + dfs(len - 1, ismax && i == maxx, isup, i, false)) % MOD;
        //若还在前导零的范围内并且i还是0，则lead_zero继续为false
        else if (!lead_zero)
            ans = (ans + dfs(len - 1, ismax && i == maxx, isup, i, true)) % MOD;
        //若找到了可以处理的数字并且这个数字之前是前导零
        else if (i == last)
            ans = (ans + dfs(len - 1, ismax && i == maxx, isup, i, true)) % MOD;
        //若i与前一个相同
        else
            ans = (ans + dfs(len - 1, ismax && i == maxx, i > last ? 2 : 1, i,
                             true)) %
                  MOD;
        //若不同
    }
    if (!ismax)
        dp[len][last][isup] = ans;
    return ans;
}
ll solve(char str[]) {
          
   
    ll len = 0;
    for (ll i = strlen(str) - 1; i >= 0; i--)
        digit[++len] = str[i] - 0;
    return dfs(len, true, 0, -1, false);
}
void init() {
          
   
    memset(dp, -1, sizeof dp);
}
int main() {
          
   
    int t;
    scanf("%d", &t);
    init();
    while (t--) {
          
   
        char n[NN];
        scanf("%s", n);
        printf("%lld
", solve(n));
    }
    return 0;
}