欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[hdu6148][Valley Numer]

程序员文章站 2022-07-08 20:00:00
"hdu6148" 思路 一个数位dp模板题,注意判断前导0。用一个bz来记录当前是应该增还是可增可减。然后排除不满足条件的情况并进行dp即可。 代码 cpp include include include using namespace std; typedef long long ll; con ......

思路

一个数位dp模板题,注意判断前导0。用一个bz来记录当前是应该增还是可增可减。然后排除不满足条件的情况并进行dp即可。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1000000007;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char c[110];
int a[110],n;
ll f[110][20][5];
ll dfs(int pos,int lst,int limit,int fx,int rea) {//fx为0表示可增可减,fx为1表示只能增 
    if(pos==n+1) return rea;
    if(f[pos][lst][fx]!=-1&&!limit&&rea) return f[pos][lst][fx];
    int up=limit?a[pos]:9;
    ll ans=0;
    for(int i=up;i>=0;--i) {
        if(fx==1&&i<lst) break;
        int p=fx;
        if(i>lst) p=1;
        if(!rea) p=0;
        ans+=dfs(pos+1,i,limit&&i==up,p,rea||i);
        ans%=mod;
    }
    if(!limit) f[pos][lst][fx]=ans;
    return ans;
}
int main() {
    int t=read();
    while(t--) {
        scanf("%s",c+1);
        n=strlen(c+1);
        for(int i=1;i<=n;++i)
            a[i]=c[i]-'0'; 
        memset(f,-1,sizeof(f));
        printf("%lld\n",dfs(1,10,1,0,0));
    }
    return 0;
}