首页 > 代码库 > HDU 2089 dfs
HDU 2089 dfs
数位DP
dfs写法 时间 9^9 也不会超时
感觉数据水了
#include <iostream> #include<string.h> #include<stdio.h> using namespace std ; int dig[10],f[10][2]; int calc(int n) { int cnt=0; while(n) { cnt++; n/=10; } return cnt; } int dfs(int i,int s,int e) //e为0 那么可以随便填 e为1 前面一位为6 { if(i==0) return 1; if(!e&&f[i][s]!=-1) //可以随便填 数据也有 return f[i][s]; int ans=0; int u=e?dig[i]:9; //1的话不能随便填 for(int j=0;j<=u;j++) { if(j==4||(s&&j==2)) continue; ans+=dfs(i-1,j==6,e&&j==u); } return e?ans:f[i][s]=ans;//记忆化一下 } void cald(int n,int len) { for(int i=1;i<=len;i++) { dig[i]=n%10; n=n/10; } } int solve(int n) { int len=calc(n); cald(n,len); int ans=dfs(len,0,1); return ans; } int main() { int n,m ; memset(f,-1,sizeof(f)) ; while(~scanf("%d%d",&n,&m)) { if(n==0 && m==0) break ; printf("%d\n",solve(m)-solve(n-1)) ;//用[0,m]-[0,n)即可得到区间[n,m] } return 0 ; }
HDU 2089 dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。