HDU 6148 Valley Numer 数位DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6148

题意：如题。

解法：裸数位DP，dp[pos][pre][sta]表示当前在pos位，前一位的数字是pre,当前状态是上升还是下降的合法的数的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 110;
const int mod = 1e9+7;
LL dp[maxn][12][2];
LL digit[maxn];
LL dfs(int pos, int sta, int pre, int lim)
{
    if(pos<1) return 1;
    if(!lim&&~dp[pos][pre][sta]) return dp[pos][pre][sta];
    int jud = lim?digit[pos]:9;
    LL ans = 0;
    if(sta){
        for(int i=pre; i<=jud; i++){
            ans += dfs(pos-1, 1, i, lim&&i==jud);
            ans %= mod;
        }
    }else{
        for(int i=0; i<=jud; i++){
            if(i>pre){
                ans += dfs(pos-1,1,i,lim&&i==jud);
                ans %= mod;
            }
            else{
                if(!i&&pre==10)
                    ans += dfs(pos-1,0,10,lim&&i==jud);
                else
                    ans += dfs(pos-1,0,i,lim&&i==jud);
                ans %= mod;
            }
        }
    }
    if(!lim) dp[pos][pre][sta] = ans;
    return ans;
}
LL f(char s[])
{
    int len = strlen(s);
    for(int i=0; i<len; i++){
        digit[len-i] = s[i]-'0';
    }
    return dfs(len, 0, 10, 1);
}
char s[110];
int main()
{
    memset(dp, -1, sizeof(dp));
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", s);
        printf("%lld
", (f(s)-1+mod)%mod);
    }
    return 0;
}