首页 > 代码库 > hdu2089(数位dp)
hdu2089(数位dp)
题意:求区间内不含62和4的数的个数;
解法:数位dp。int dfs(int pos,int pre,bool limit,bool have),pos表示dp到的数位位置,pre表示前一个数位的数字,limit表示到此时数是否有下降(此位取数字是否受限制的意思),have表示之前是否有62;4的排除是靠在每次枚举下一位i时不取4即可;每个case的dp值都是一样的,所以只需要计算一遍。
代码:
/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=10100; const int INF=1000000007; int dp[15][12]; int num[20]; int p=0; int dfs(int pos,int pre,bool limit,bool have) { if(pos==0) return !have; if(have) return 0; if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre]; int en=limit?num[pos-1]:9; int ans=0; for(int i=0; i<=en; i++) { if(i==4)continue; ans+=dfs(pos-1,i,limit&&i==en,(pre==6&&i==2)); } if(!limit) return dp[pos][pre]=ans; else return ans; } int getans(int t) { if(t==0) return 0; p=0; while(t) { num[p++]=t%10; t/=10; } int ans=0; for(int i=0; i<=num[p-1]; i++) { if(i==4) continue; ans+=dfs(p-1,i,i==num[p-1],0); } return ans-1; } int main() { int l,r; memset(dp,-1,sizeof dp); while(scanf("%d%d",&l,&r)==2) { if(r==0&&l==0) break; cout<<getans(r)-getans(l-1)<<'\n'; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。