POJ 3252 Round Numbers 数位DP .

题目地址：http://poj.org/problem?id=3252

这次要包含lead表示是否有前导0，因为 00001 和 10000 是不一样的，而他们在状态表示的时候却一样，这样子就状态重叠了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxp=33;
typedef long long LL;
LL d[maxp][maxp][maxp];
int digit[maxp];
LL DFS(int pos,int num0,int num1,bool lead,bool limit)
{     //位置  |   0的数量 | 1的数量 | 是否有前导0 |是否边界if(pos==-1) return lead||num0>=num1;LL& ans=d[pos][num0][num1];   //直接保存引用，防止多维数组多次寻址浪费时间if(!limit && !lead && ans!=-1) return ans;LL temp=0;int up=limit?digit[pos]:1;for(int i=0;i<=up;i++){if(lead){if(i==1) temp+=DFS(pos-1,num0,num1+1,false,limit&&up==i);else 	 temp+=DFS(pos-1,num0,num1,true,limit&&up==i);}else {if(i==1) temp+=DFS(pos-1,num0,num1+1,false,limit&&up==i);else     temp+=DFS(pos-1,num0+1,num1,false,limit&&up==i);}}if(!limit&&!lead) ans=temp;return temp;
}
LL solve(LL x)
{int len=0;while(x){digit[len++]=x&1;x>>=1;}return DFS(len-1,0,0,true,true);
}
int main(int argc, char const *argv[])
{LL s,e;memset(d,-1,sizeof(d));while(scanf("%lld%lld",&s,&e)!=EOF)cout<<solve(e)-solve(s-1)<<endl;return 0;
}