首页 > 代码库 > POJ 2282 Counting Problem
POJ 2282 Counting Problem
http://poj.org/problem?id=2282
题意:问[a,b]内 数字[0~9]分别出现多少次? a,b<=1e9.
数位DP dp[len][sta]:当前长度为len 数字y的初始状态为sta时,数字y共出现了多少次?
枚举当前位 如果为i!=num ,len-1位y的初始状态为sta
如果i==num ,len-1位y的初始状态为sta+1
当前位<0 则返回y的出现次数
#include <iostream> #include <cstring> #include <cstdio> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=3e2+20; ll a[N],num; ll dp[N][N]; int dfs(int pos,int sta,bool lead,bool limit) { if(pos==-1) return sta; if(!lead&&!limit&&dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:9; int res=0; for(int i=0;i<=up;i++) { if(lead&&i==0) res+=dfs(pos-1,sta,true,limit&&i==a[pos]); else res+=dfs(pos-1,sta+(i==num),false,limit&&i==a[pos]); } if(!lead&&!limit) dp[pos][sta]=res; return res; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,0,true,true); } int main() { int a,b; memset(dp,-1,sizeof(dp)); while(cin>>a>>b&&(a+b)) { if(a>b) swap(a,b); num=0; cout<<solve(b)-solve(a-1); for(num=1;num<=9;num++) cout<<‘ ‘<<solve(b)-solve(a-1); cout<<endl; } return 0; }
POJ 2282 Counting Problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。