这种数位DP还是用刷表法比较好，记忆化搜索不太好写。
/************************************************************** PRoblem: 1833 User: vermouth Language: C++ Result: Accepted Time:40 ms Memory:9496 kb****************************************************************/ #include<cstdio>#include<iostream>#include<cstring>#define ll long longusing namespace std;const int maxn=100010;ll f[100][100][100],bin[100],ret[100],a,b,ans;int d[maxn];ll solve(ll x,int flag){ int cnt1=0;ll cur=x; memset(d,0,sizeof(d)); while(x){d[++cnt1]=x%10;x/=10;} for(int i=1;i<cnt1;i++) for(int j=1;j<=9;j++) { for(int k=0;k<=9;k++) { ret[k]+=(f[i][j][k]*flag); } } int cnt3=cnt1; while(cnt3) { for(int i=0;i<d[cnt3];i++){ if(!i&&cnt3==cnt1) continue; for(int j=0;j<=9;j++) ret[j]+=f[cnt3][i][j]*flag; } ret[d[cnt3]]+=(cur%bin[cnt3]+1)*flag; cnt3--; }}int main(){ scanf("%lld%lld",&a,&b); bin[1]=1; for(int i=2;i<=13;i++) bin[i]=bin[i-1]*10; for(int i=0;i<=9;i++) f[1][i][i]=1; for(int i=2;i<=13;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) { for(int z=0;z<=9;z++) f[i][j][z]+=f[i-1][k][z]; f[i][k][k]+=bin[i-1]; } solve(b,1); solve(a-1,-1); for(int i=0;i<9;i++) printf("%lld ",ret[i]); printf("%lld",ret[9]); return 0;}新闻热点
疑难解答
