首页 > 代码库 > poj2282(数位dp)
poj2282(数位dp)
题意:计算a-b中各个数字出现的个数;
解法:数位dp(思想都是先算1-b的个数,然后减掉1-a中的个数),1-9数字的计算和前边计算1的那一篇数位dp差不多,计算0时候要加一维表示前缀是否全是0;
代码:
/****************************************************** * 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[20][20][2]; int dp0[20][20][2][2]; int tool[20]; LL fac[20]; int com=0; int st,en; void init() { fac[0]=1;fac[1]=10; for(int i=2;i<10;i++) fac[i]=fac[i-1]*10; } int dfs0(int pre,int now,bool iflow,bool ifall0) { if(pre==0) return now==0; if(dp0[pre][now][iflow][ifall0]!=-1) return dp0[pre][now][iflow][ifall0]; int en=iflow? 9: tool[pre-1]; int ans=0; if(now==0&&!ifall0&&!iflow) ans+=com%fac[pre]+1; if(now==0&&!ifall0&&iflow) ans+=fac[pre]; for(int i=0;i<=en;i++) ans+=dfs0(pre-1,i,iflow||i!=en,ifall0&&i==0); return dp0[pre][now][iflow][ifall0]=ans; } int dfs(int pre,int now,bool iflow,int who) { if(pre==0) return now==who; if(dp[pre][now][iflow]!=-1) return dp[pre][now][iflow]; int en=iflow? 9 : tool[pre-1]; int ans=0; if(now==who&&iflow) ans+=fac[pre]; if(now==who&&(!iflow)) ans+=com%fac[pre]+1; for(int i=0;i<=en;i++) ans+=dfs(pre-1,i,iflow||(i!=en),who); return dp[pre][now][iflow]=ans; } int solve(int k,int t) { com=k; int p=0; if(k==0&&t==0) return 1; while(k) { tool[p++]=k%10; k/=10; } int ans=0; if(t==0) { memset(dp0,-1,sizeof dp0); ans+=dfs0(p-1,0,1,1); for(int i=1;i<=tool[p-1];i++) ans+=dfs0(p-1,i,i!=tool[p-1],0); return ans; } else { memset(dp,-1,sizeof dp); for(int i=0;i<=tool[p-1];i++) ans+=dfs(p-1,i,i!=tool[p-1],t); return ans; } } int main() { init(); while(scanf("%d%d",&en,&st)==2) { if(st<en) swap(st,en); if(st==0&&en==0) break; cout<<solve(st,0)-solve(en-1,0); for(int i=1; i<10; i++) { cout<<" "<<solve(st,i)-solve(en-1,i); } cout<<‘\n‘; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。