首页 > 代码库 > LightOJ 1140 How Many Zeroes
LightOJ 1140 How Many Zeroes
题意:写出一个给定区间的每个数,求出一共写了多少个零。
解法:数位DP,定义dp[len][flag][num]:len的定义为数位的长度,flag定义为前导0和没有前导0的两种状态,num定义为写的满足条件的0的个数。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 #define exp 1e-10 9 #define PI 3.141592654 10 using namespace std; 11 typedef long long LL; 12 LL digit[21]; 13 LL dp[21][2][21]; 14 LL dfs(LL len,bool flag,LL p,LL p2,bool fp) 15 { 16 if (!len) 17 { 18 if (!flag) 19 return p2-p; 20 else return 0; 21 } 22 if (!fp && dp[len][flag][p2-p]!=-1) return dp[len][flag][p2-p]; 23 LL ret=0; 24 LL fpmax= fp ? digit[len] : 9 ; 25 for (LL i=0 ;i<=fpmax ;i++) 26 { 27 bool ok= i==0 ? true : false; 28 LL temp; 29 if (i==0) temp=1 ; else temp=0 ; 30 ret += dfs(len-1,flag&&ok,flag?p+temp:p ,p2+temp,fp&&i==fpmax); 31 } 32 if (!fp) return dp[len][flag][p2-p]=ret; 33 return ret; 34 } 35 LL f(LL n) 36 { 37 if (n==-1) return -1; 38 if (n==0) return 0; 39 LL len=0; 40 while (n) 41 { 42 digit[++len]=n%10; 43 n /= 10; 44 } 45 return dfs(len,true,0,0,true); 46 } 47 int main() 48 { 49 int t; 50 int ncase=1; 51 cin>>t; 52 while (t--) 53 { 54 LL a,b; 55 scanf("%lld%lld",&a,&b); 56 memset(dp,-1,sizeof(dp)); 57 printf("Case %d: %lld\n",ncase++,f(b)-f(a-1)); 58 } 59 return 0; 60 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。