首页 > 代码库 > uestc 250 数位dp(水)
uestc 250 数位dp(水)
/* 数位dp 水题 开两维一个记录长度,一个记录上一个数 */ #include<stdio.h> #include<string.h> #define N 13 int dp[N][N]; int digit[N]; int dfs(int len,int cnt,int ok) { if(!len)return 1; if(!ok&&dp[len][cnt]!=-1) return dp[len][cnt]; int ans=0,i,maxx=ok?digit[len]:9; for(i=0;i<=maxx;i++) { if(cnt==11&&i==0) {//因为不含前导0,所以特殊判断 ans+=dfs(len-1,cnt,ok&&i==maxx); } else if(cnt-i>=2||i-cnt>=2) ans+=dfs(len-1,i,ok&&i==maxx); } if(!ok) dp[len][cnt]=ans; return ans; } int f(int n) { int len=0; while(n) { digit[++len]=n%10; n/=10; } return dfs(len,11,1); } int main() { int n,m; memset(dp,-1,sizeof(dp)); while(scanf("%d%d",&n,&m)!=EOF) { printf("%d\n",f(m)-f(n-1)); } return 0;}
uestc 250 数位dp(水)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。