【算法】数位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=,MOD=;
ll f[maxn][][],a[maxn],n; ll dfs(ll pos,ll state,ll limit,ll pre){
if(pos==-){if(~pre)return ;else return ;}
if(!limit&&~pre&&~f[pos][state][pre])return f[pos][state][pre];
ll up=limit?a[pos]:;
ll ans=;
for(int i=;i<=up;i++){
if(pre==-&&i==)ans=(ans+dfs(pos-,state,limit&&i==up,pre))%MOD;else
if(pre==-&&i!=)ans=(ans+dfs(pos-,state,limit&&i==up,i))%MOD;else
if(state==)ans=(ans+dfs(pos-,i>pre,limit&&i==up,i))%MOD;else
if(state==&&i>=pre)ans=(ans+dfs(pos-,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,-,sizeof(f));
while(T--){
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;i++)a[n-i]=s[i]-'';
printf("%lld\n",dfs(n-,,,-));
}
return ;
}
递推有病啊……细节一大堆，对拍调了一个又一个的错误才AC了，呜呜呜。
主要细节在逐位确定的时候：
1.如果前面递增了，后面枚举数位就不准枚举比前面小的。
2.如果前面递增又递减了，直接退出。
3.如果前面不递增且该位不大于前一位，后面才能取递减的值。
数位DP的逐位递推都是根据高位信息确定低位信息的哦！能干很多事（我选择记忆化搜索QAQ）
#include<cstdio>
#include<cstring>
const int MOD=1e9+,maxn=;
int f[maxn][maxn][],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=;i<n;i++)for(int j=;j<=;j++)p(ans,M(f[i][j][]+f[i][j][]));
for(int j=;j<a[n];j++)p(ans,M(f[n][j][]+f[n][j][]));
bool ok=;
for(int i=n-;i>=;i--){
for(int j=;j<a[i];j++)if(ok||j>=a[i+]){
if(ok&&j<=a[i+])p(ans,M(f[i][j][]+f[i][j][]));
else p(ans,f[i][j][]);
}
if(!ok&&a[i]<a[i+])break;
if(a[i]>a[i+])ok=;
}
}
char s[maxn];
int main(){
int T;scanf("%d",&T);int N=;
for(int j=;j<=;j++)f[][j][]=;
for(int i=;i<=N;i++){
for(int j=;j<=;j++){
for(int k=;k<=;k++){
if(j>k)p(f[i][j][],f[i-][k][]);
else p(f[i][j][],f[i-][k][]);
if(j>=k)p(f[i][j][],f[i-][k][]);
}
}
}
while(T--){
scanf("%s",s+);n=strlen(s+);
for(int i=;i<=n;i++)a[i]=s[n-i+]-'';a[n+]=;
for(int i=;i<=n+;i++)if(a[i]!=){
if(i==n+)n++;
a[i]++;for(int j=i-;j>=;j--)a[j]=;
break;
}
ans=;solve();
printf("%d\n",ans);
}
return ;
}