poj 3252 (디지털 dp)

전송문
문제 풀이:
디지털 dp 기초 문제.선도 0의 특수 처리에 주의하시오.
P.S. 공간 최적화: dfs 함수 중 0과 1의 두 계수 매개 변수는 cnt로 합쳐서 0과 1의 차이를 나타낼 수 있으며 계산할 때 전체 오른쪽을 32자리로 이동하면 된다(아래 표시가 음인 것을 방지한다)

#include
#include
#include
#include
using namespace std;
int s,t,dp[33][33][33],b[33];//    ，  0     ，  1     。
int dfs(int pos,int zer,int one,bool first,bool lim) {//    0
	if (pos==-1) return zer>=one;
	if (!first&&!lim&&~dp[pos][zer][one]) return dp[pos][zer][one];
	int end=lim?b[pos]:1,ans=0;
	for (int i=0;i<=end;++i) {
		if (first) {
			if (i) ans+=dfs(pos-1,0,1,0,lim&&i==end);
			else ans+=dfs(pos-1,1,0,1,lim&&i==end);
        } else ans+=dfs(pos-1,zer+(!i),one+(i&1),0,lim&&i==end);
	}
	if (!lim&&!first) dp[pos][zer][one]=ans;
	return ans;
}
inline int work(int x) {
	int len=0;
	while (x) {
		b[len++]=x&1;
		x>>=1;
	}
	return dfs(len-1,0,0,1,1);
}
int main() {
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&s,&t);
	printf("%d
",work(t)-work(s-1));
	return 0;
}