hdu3555 Bomb(数位dp)

hdu3555

题目

求给定n以下的含连续49的数字的个数。

思路

设置一个pre表示有没有4，在dfs中转移的时候9要用到，貌似要考虑0的问题。

代码

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