hdu2089 不要62(数位dp)

hdu2089

题目

求给定范围内没有4，没有连着的62的数字数目。

思路

有了dfs套路再做这道题就很简单了23333，按照题意填空就可以了233.

代码

#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<stack> using namespace std; typedef unsigned long long ll; int dp[10][2]; int dis[10]; int dfs(int len,int pre,int lim) { if(len<0) return 1; if(!lim&&dp[len][pre]!=-1) return dp[len][pre]; int res=0; int u=lim?dis[len]:9; for(int s=0; s<=u; s++) { if(s!=4&&!(pre&&s==2)) { res+=dfs(len-1,s==6,lim&&s==u); } } if(!lim) return dp[len][pre]=res; return res; } int n,m; int solve(int u) { int len=0; while(u) { dis[len++]=u%10; u/=10; } return dfs(len-1,0,1); } int main() { while(scanf("%d %d",&n,&m)) { if(n==0&&m==0) break; memset(dp,-1,sizeof(dp)); printf("%d\n",solve(m)-solve(n-1)); } return 0; }