【算法】数位DP
【题意】定义V-number为从左到看单位数字未出现先递增后递减现象的数字，求0~N中满足条件的数字个数。T<=200,lenth(n)<=100
【题解】百度之星2017复赛，作为送分题出现，拿来练数位DP模板了。
位数多，读入记得用字符串。
记忆化要将有关变量全部纳入。
需要取模的时候别习惯性写"+="，特别是竞速赛，改起来很难受。
-1的变量前加~就和0一样了。
最后自己造数据测试了一下，记忆化搜索的速度简直全面碾压递推啊！（从此坚定了信仰）
#include<cstdio> #include<algorithm> #include<cstring> #include<cctype> #define ll long long using namespace std; const ll maxn=110,MOD=1000000007; ll f[maxn][2][10],a[maxn],n; ll dfs(ll pos,ll state,ll limit,ll pre){ if(pos==-1){if(~pre)return 1;else return 0;} if(!limit&&~pre&&~f[pos][state][pre])return f[pos][state][pre]; ll up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++){ if(pre==-1&&i==0)ans=(ans+dfs(pos-1,state,limit&&i==up,pre))%MOD;else if(pre==-1&&i!=0)ans=(ans+dfs(pos-1,state,limit&&i==up,i))%MOD;else if(state==0)ans=(ans+dfs(pos-1,i>pre,limit&&i==up,i))%MOD;else if(state==1&&i>=pre)ans=(ans+dfs(pos-1,state,limit&&i==up,i))%MOD;//取模！！！ } if(!limit&&~pre)f[pos][state][pre]=ans;//记忆化：当前状态和pos，state，pre三者都有关系！！！ return ans; } char s[maxn]; int main(){ ll T; scanf("%lld",&T); memset(f,-1,sizeof(f)); while(T--){ scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++)a[n-i]=s[i]-'0'; printf("%lld ",dfs(n-1,0,1,-1)); } return 0; }
递推有病啊……细节一大堆，对拍调了一个又一个的错误才AC了，呜呜呜。
主要细节在逐位确定的时候：
1.如果前面递增了，后面枚举数位就不准枚举比前面小的。
2.如果前面递增又递减了，直接退出。
3.如果前面不递增且该位不大于前一位，后面才能取递减的值。
数位DP的逐位递推都是根据高位信息确定低位信息的哦！能干很多事（我选择记忆化搜索QAQ）
#include<cstdio> #include<cstring> const int MOD=1e9+7,maxn=110; int f[maxn][maxn][2],ans,n,a[maxn]; int M(int x){return x>=MOD?x-MOD:x;} void p(int &x,int y){x=(x+y>=MOD?x+y-MOD:x+y);} void solve(){ for(int i=1;i<n;i++)for(int j=1;j<=9;j++)p(ans,M(f[i][j][0]+f[i][j][1])); for(int j=1;j<a[n];j++)p(ans,M(f[n][j][0]+f[n][j][1])); bool ok=1; for(int i=n-1;i>=1;i--){ for(int j=0;j<a[i];j++)if(ok||j>=a[i+1]){ if(ok&&j<=a[i+1])p(ans,M(f[i][j][0]+f[i][j][1])); else p(ans,f[i][j][0]); } if(!ok&&a[i]<a[i+1])break; if(a[i]>a[i+1])ok=0; } } char s[maxn]; int main(){ int T;scanf("%d",&T);int N=105; for(int j=0;j<=9;j++)f[1][j][0]=1; for(int i=2;i<=N;i++){ for(int j=0;j<=9;j++){ for(int k=0;k<=9;k++){ if(j>k)p(f[i][j][1],f[i-1][k][0]); else p(f[i][j][0],f[i-1][k][0]); if(j>=k)p(f[i][j][1],f[i-1][k][1]); } } } while(T--){ scanf("%s",s+1);n=strlen(s+1); for(int i=1;i<=n;i++)a[i]=s[n-i+1]-'0';a[n+1]=0; for(int i=1;i<=n+1;i++)if(a[i]!=9){ if(i==n+1)n++; a[i]++;for(int j=i-1;j>=1;j--)a[j]=0; break; } ans=0;solve(); printf("%d ",ans); } return 0; }