首页 > 代码库 > hud 2089 不要62 (数位dp)
hud 2089 不要62 (数位dp)
#include<stdio.h> #include<string.h> #include<math.h> #define max 10 int dp[max][3]; int number[max]; //dp[i][0] 前i位数中不符合要求的总个数 //dp[i][1] 前i位数中最高位是2的个数 //dp[i][2] 前i位数中存在含4和有连续62的个数 void init() { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<max;i++) { dp[i][0]=dp[i-1][0]*9-dp[i-1][1]; //除了4 并不含6+2..的 dp[i][1]=dp[i-1][0]; //2+, dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1]; } } int len_num(int num) { int i=0; memset(number,0,sizeof(number)); while(num) { ++i; number[i]=num%10; num/=10; } return i; } int solve(int num) { int i,flag=0,count=0; int len=len_num(num); number[len+1]=0; for(i=len;i>0;i--) { count+=dp[i-1][2]*number[i]; if(flag) { count+=dp[i-1][0]*number[i]; } else { if(number[i]>4) count+=dp[i-1][0]; if(number[i]>6) count+=dp[i-1][1]; if(number[i]>2&&number[i+1]==6) count+=dp[i][1];//等于62是这个本身不用算在里面 只有大于2才会完全计算 if((number[i]==2&&number[i+1]==6)||number[i]==4) flag=1; } } return num-count; } int main(void) { init(); int n,m,i,j; while(scanf("%d%d",&n,&m)&&n&&m) { printf("%d\n",solve(m+1)-solve(n)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。