首页 > 代码库 > hdu2089:不要62(基础数位dp)
hdu2089:不要62(基础数位dp)
题意:规定一个合法的号码不能含有4或者是连续的62
给定区间[n,m] 问此区间内合法的号码的个数
分析:数位dp
dp[i][j]代表 最高位为 j 的 i 位数有多少个合法的
然后按题目规则进行转移即可
dp结束后,再统计范围内的总数,最后打表输出
代码:
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define MAX 100000000int n,k,m;int ans[1000010];int dp[10][10];int fun(int x){ int t=0; int res=0; int a[10]; while(x) { a[t++]=x%10; x/=10; } for(int i=t;i;i--) { for(int j=0;j<a[i-1];j++) { if((!(j==2&&a[i]==6))) res+=dp[i][j]; } if((a[i-1]==2&&a[i]==6)||a[i-1]==4) break; } return res;}void DP(){ for(int i=0;i<=9;i++) { if(i!=4) dp[1][i]=1; else dp[1][i]=0; } for(int i=2;i<=7;i++) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { if(j!=4&&(j!=6||k!=2)) dp[i][j]+=dp[i-1][k]; } } }}void solve(){ for(int i=1;i<=1000001;i++) { ans[i]=fun(i); }}int main(){ DP(); solve(); while(scanf("%d%d",&n,&m)&&(n+m)) { printf("%d\n",ans[m+1]-ans[n]); } return 0;}
hdu2089:不要62(基础数位dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。