首页 > 代码库 > poj3252数位dp
poj3252数位dp
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;int dp[55][55][55];int up[100];int dfs(int now,int len0,int len1,int flag){ if(now==-1) return len0>=len1; if(!flag&&dp[now][len0][len1]!=-1) return dp[now][len0][len1]; int limit= flag?up[now ]:1 ,ret=0 ; for(int i = 0;i <= limit;i++){ int len00=len0;int len11=len1; if(i==0&&len1) len00=len0+1; if(i==1) len11=len1+1; ret+=dfs(now-1,len00,len11,flag&&i==limit) ; } if(!flag) dp[now][len0][len1]=ret; return ret;}int solve(int x){ int len=-1; while(x){ up[++len]=x%2; x/=2; } return dfs(len,0,0,1);}int main(){ int n, m; memset(dp,-1,sizeof(dp)); while(cin>>n>>m){ cout<<solve(m) - solve(n-1)<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。