[USACO2003 Dec]Cow Queueing数数的梦 (基础水数位DP带注释！)

本文主要是介绍[USACO2003 Dec]Cow Queueing数数的梦 (基础水数位DP带注释！)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.tju.edu.cn/toj/showp2839.html(真的找不到链接了)

题目大意：

给你一个范围A~B，求出在整数A 到B之间，0到9这十个数字，分别出现了多少次？

1≤A，B≤10^18

样例输入  129 137

样例输出  1 10 2 9 1 1 1 1 0 1

题解：

数位DP

我的第一道数位DP。。尽管是基础水题但是搞了好久ORZ &&感谢关大学霸%%%！

范围A~B，那么就先算出在1~B中这十个数字分别出现了多少次。再算出在1~A-1中各出现了多少次，然后相减就好了。

[我都是 最高位从1开始...就是诶待会看下图]

以样例为例。先说一下什么叫上限边缘。

假设算的是1~137中各个数的出现次数。现在做到了第2位，如果前面枚举的是1，那么就处于上限边缘。枚举当前位，即第2位为3的话，仍处于上限边缘，而为0~2的话就不在上限边缘了。

然后就用图说明一下bit[]和ret[]存的是什么好了。其他的代码里有，很多很多注释！怕自己以后看不懂...

...bit[]就不画了= =，意思也差不多。bit[i]=10^i。因为还没限制，所以可以填的总数就是bit[后面有几位].

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;LL f[20][2][2];
//f[i][flag][zero]表示搞到第i位 flag-0/1 zero-0/1的时候某数的数目
//flag表示该位是不是在上限边缘 zero表示目前是否还是前导零
LL d[10],bit[20],ret[20];
char s[20];int len;
LL dfs(int x,int i,int flag,int zero)
{if (f[i][flag][zero]!=-1) return f[i][flag][zero];//记忆化↑ 不加超时if (i>len) return 0;LL ans=0;if (flag)//如果前面的部分处于上限边缘{int j=s[i]-'0';//该位的上限是多少for (int k=0;k<j;k++)//枚举该位填什么{ans+=dfs(x,i+1,0,zero&(k==0));//不是上限的边缘↑了  ↑就是看看还是不是前导0if (k==x && !(zero&(k==0))) ans+=bit[len-i];//如果k是要统计次数的那个数字 而且不是在前导零的时候//而且还不是在上限的边缘！//那么后面几位的数字有多少种填法x就出现了几次}ans+=dfs(x,i+1,1,zero&(j==0));//该位填上限就仍在上限边缘if (j==x && !(zero && (j==0))) ans+=ret[i]+1;//如果填的是要统计次数的那个数字 而且不是在前导零的时候//那么后面的数字最多有多少种填法x就出现了几次（受限的哦！}else//↓就没有限制啦随便填 该统计的时候跟上面同理统计{for (int k=0;k<=9;k++){ans+=dfs(x,i+1,0,zero&(k==0));if (k==x && !(zero && (k==0))) ans+=bit[len-i];}}f[i][flag][zero]=ans;//记忆化return ans;
}
void cl()//把A减1 其实这样最高位可能变成了0 
//但是我的最高位是从1开始往后存的 所以没办法..(懒得全部往前挪一下= =
{int t=len;while (t>1 && s[t]=='0'){s[t]='9';t--;}s[t]--;
}
int main()
{//freopen("dream.in","r",stdin);//freopen("dream.out","w",stdout);int i;memset(d,0,sizeof(d));scanf("%s ",s+1);bit[0]=1;for (i=1;i<=18;i++) bit[i]=bit[i-1]*10;len=strlen(s+1);cl();ret[len]=0;for (i=len-1;i>=1;i--) ret[i]=(s[i+1]-'0')*bit[len-i-1]+ret[i+1];for (i=0;i<=9;i++){memset(f,-1,sizeof(f));d[i]-=dfs(i,1,1,1);}scanf("%s",s+1);len=strlen(s+1);ret[len]=0;for (i=len-1;i>=1;i--) ret[i]=(s[i+1]-'0')*bit[len-i-1]+ret[i+1];for (i=0;i<=9;i++){memset(f,-1,sizeof(f));d[i]+=dfs(i,1,1,1);}for (i=0;i<9;i++)printf("%d ",d[i]);printf("%d\n",d[9]);return 0;
}

这篇关于[USACO2003 Dec]Cow Queueing数数的梦 (基础水数位DP带注释！)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---