首页 > 代码库 > hdu2089不要62(数位dp)
hdu2089不要62(数位dp)
题目大意就是数字中不能出现 62 和4
代码:
/************************************************************************* > File Name: 2089.cpp > Author: minshik > Created Time: 2014年05月22日 星期四 00时52分49秒 ************************************************************************/ //数位dp // #include <string> #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> #include <list> #include <map> #include <queue> #include <cmath> using namespace std; int dp[10][3]; //i,j 表示i位 0:没有,1:最后一个是6,2:已经有不符和了 int DP(int n) { bool flag = false; int s[15]; int idx = 0; int x = n; while(x) { s[++idx] = x%10; x/=10; } s[idx+1] =0; int ans = 0; for(int i=idx;i>0;i--) { ans += (dp[i-1][2]*s[i]); //之前已经有不符和 if( flag )ans+=(dp[i-1][0]*s[i]); else { if( s[i] >4 ) ans+= dp[i-1][0]; if( s[i] > 6 ) ans+=dp[i-1][1]; if( s[i+1]==6 && s[i]>2 ) ans+=dp[i][1]; } if( s[i]==4 || s[i+1]==6&&s[i]==2 ) { flag = true; } } return n-ans; } int main() { dp[0][0] = 1; for(int i=1;i<=8;i++) { dp[i][0] = dp[i-1][0]*9-dp[i-1][1]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]*10; } int n,m; while(scanf("%d %d",&n,&m)!=EOF) { if( n==0 && m ==0 )break; printf("%d\n",DP(m+1)-DP(n)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。