hdu6148 Valley Number（数位dp）

题目链接： hdu6148 ( Valley Numer )

\(dp[i][j][state]\) 代表 \(i\) 位数、首位为 \(j\) 、且状态为 \(state\) 的数的个数。 \(state\) 取 \(0\) 代表严格递减， \(1\) 代表严格递增， \(2\) 代表严格先减后增， \(3\) 代表各位相等。（此处的严格代表必须有增减的趋势，增减的过程中可以出现相等数字）

则根据 \(i-1\) 的状态可推出 \(i\) 的状态。

\(AC\) 代码：

/**
 * hdu6148 Valley Number
 *
 */

#include <iostream>
#include <climits>
#include <cmath>
#include <iomanip>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 105;
LL dp[N][10][4];  // dp[i][j][state]代表 i位数 j为首位 state为状态（0代表\，1代表/，2代表V，3代表__）
const int mod = 1e9+7;

void init()
{
    for (int j = 0; j < 10; ++j) dp[1][j][3] = 1;
    for (int i = 2; i < N; ++i) {
        for (int j = 0; j < 10; ++j) {
            for (int k = 0; k < 10; ++k) {
                dp[i][j][0] += (j>=k?dp[i-1][k][0]:0) + (j>k?dp[i-1][k][3]:0);
                dp[i][j][1] += (j<=k?dp[i-1][k][1]:0) + (j<k?dp[i-1][k][3]:0);
                dp[i][j][2] += (j>=k?dp[i-1][k][2]:0) + (j>k?dp[i-1][k][1]:0);
                dp[i][j][3] += (j==k?dp[i-1][j][3]:0);
                dp[i][j][0] %= mod;
                dp[i][j][1] %= mod;
                dp[i][j][2] %= mod;
                dp[i][j][3] %= mod;
            }
        }
    }
}

char d[N];
int calc()
{
    LL res = 0;
    int len = 0;
    for (int i = 1; d[i]; ++i) {
        d[i]^=‘0‘;
        ++len;
    }
    reverse(d+1, d+1+len);
    
    // 手动加一
    int carry = 1;
    for (int i = 1; i <= len; ++i) {
        if (++d[i] > 9) d[i]-=10;
        else {carry = 0; break;}
    }
    if (carry) d[++len] = 1;
    
    d[len+1] = d[len];
    int state = 3;
    for (int i = len; i; --i) {
        for (int j = 0; j < d[i]; ++j) {
            if (i == len && j == 0) continue;  // 首位为0的情况单独处理。
            if (i == len) {
                res += dp[i][j][0];
                res += dp[i][j][1];
                res += dp[i][j][2];
                res += dp[i][j][3];
            }
            else if (state == 3) {
                if (j <= d[i+1]) res += dp[i][j][0];
                res += dp[i][j][1];
                if (j <= d[i+1]) res += dp[i][j][2];
                res += dp[i][j][3];
            }
            else if (state == 2 && j >= d[i+1]) {
                res += dp[i][j][1];
                res += dp[i][j][3];
            }
            else if (state == 1 && j >= d[i+1]) {
                res += dp[i][j][1];
                res += dp[i][j][3];
            }
            else if (state == 0) {
                if (j <= d[i+1]) res += dp[i][j][0];
                res += dp[i][j][1];
                if (j <= d[i+1]) res += dp[i][j][2];
                res += dp[i][j][3];
            }
            res %= mod;
        }

        if (state == 3) {
            if (d[i+1]>d[i]) state = 0;
            else if (d[i+1]<d[i]) state = 1;
        }
        else if (state == 0 && d[i+1]<d[i]) state = 2;
        else if (state != 0 && d[i+1]>d[i]) break;
    }

    // 处理首位为0的情况
    for (int i = 1; i < len; ++i) {
        for (int j = 1; j < 10; ++j) {
            for (int s = 0; s < 4; ++s) {
                res += dp[i][j][s];
            }
        }
    }

    res %= mod;
    return res;
}

int main()
{
    init();
    int T;
    scanf("%d%*c", &T);
    while (T--) {
        scanf("%s", d+1);
        printf("%d\n", calc());
    }

    return 0;
}

hdu6148 Valley Number（数位dp）

原文：https://www.cnblogs.com/zbhfz/p/14391633.html