首页 > 代码库 > 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;}