[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; }
上一篇: php面试题汇总