[2017百度之星程式設計大賽 - 複賽]E - hdu6148

裸的數位DP，隻需要判斷之前是否已經改變過遞增減就行了。

直接上模闆。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define ll long long
using namespace std;
const int N=110,P=1000000007;
ll f[N][2][10],a[N],n;
ll dfs(ll pos,ll st,ll lim,ll pre)
{
    if(pos==-1) {if(~pre)return 1;else return 0;}
    if(!lim&&~pre&&~f[pos][st][pre])return f[pos][st][pre];
    ll up=lim?a[pos]:9;ll ans=0;
    for(int i=0;i<=up;i++)
	{
        if(pre==-1&&i==0)ans=(ans+dfs(pos-1,st,lim&&i==up,pre))%P;else
        if(pre==-1&&i!=0)ans=(ans+dfs(pos-1,st,lim&&i==up,i))%P;else
        if(st==0)ans=(ans+dfs(pos-1,i>pre,lim&&i==up,i))%P;else
        if(st==1&&i>=pre)ans=(ans+dfs(pos-1,st,lim&&i==up,i))%P;
    }
    if (!lim&&~pre) f[pos][st][pre]=ans;
    return ans;
}
char s[N];ll T;
int main()
{
	register int i,j,l;
    scanf("%lld",&T);
    memset(f,-1,sizeof(f));
    for (l=1;l<=T;l++)
	{
        scanf("%s",s+1);
        n=strlen(s+1);
        for(i=1;i<=n;i++) a[n-i]=s[i]-'0';
        printf("%lld\n",dfs(n-1,0,1,-1));
    }
    return 0;
}