poj3252 Round Numbers[数位DP]

地址

拆成2进制位做dp记搜就行了，带一下前导0，将0和1的个数带到状态里面，每种0和1的个数讨论一下，累加即可。

WA记录：line29。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define dbg(x) cerr<<#x<<" = "<<x<<endl

 using namespace std;

 typedef long long ll;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 int f[][][][],b[];

 int l,r;

 int dp(int len,int s0,int s1,bool lead,bool limit){//ddddbg(len,s0,s1,lead);dbg(limit);

     if(s0<||s1<||s0+s1>len||(!lead&&(s0+s1)^len))return ;

     if(!len&&!s0&&!s1)return ;

     if(!limit&&~f[len][s0][s1][lead])return f[len][s0][s1][lead];

     int cnt=,num=limit?b[len]:;

     if(lead)cnt+=dp(len-,s0,s1,,limit&&!num);//填0

     else cnt+=dp(len-,s0-,s1,,limit&&!num);

     if(num)cnt+=dp(len-,s0,s1-,,limit);//填1

     return limit?cnt:f[len][s0][s1][lead]=cnt;

 }//没有乖乖套模板卡上界判断写错了

 inline int solve(int x){

     int k=,cnt=;while(x)b[++k]=x&,x>>=;
     for(register int i=;i<k;++i)for(register int j=;j<=_min(i,k-i);++j)cnt+=dp(k,i,j,,);

     return cnt;

 }

 int main(){//freopen("tmp.txt","r",stdin);//freopen("test.out","w",stdout);

     memset(f,-1,sizeof f);read(l),read(r);

     return printf("%d\n",solve(r)-solve(l-)),;

 }