数位DP求调急!!!
查看原帖
数位DP求调急!!!
587615
zqh123b楼主2023/8/19 16:59
#include<bits/stdc++.h>
using namespace std;
int x,y,tot=0,a[40],dp[40][40][40];
int dfs(int pos,int x0,int x1,bool flag1,bool flag2){
	if(dp[pos][x0][x1]!=-1&&!flag1&&!flag2)return dp[pos][x0][x1];
	if(pos==tot){
		if(x0>=x1){
			dp[pos][x0][x1]=1;
			return 1;
		}else{
			dp[pos][x0][x1]=0;
			return 0;
		}
	}
	int mx=1,ans=0;
	if(flag2)mx=a[pos+1];
	for(int i=0;i<=mx;i++){
		if(flag1&&i==0){
			ans+=dfs(pos+1,0,0,flag1,flag2&&i==a[pos+1]);
		}else{
			ans+=dfs(pos+1,x0+(i==0),x1+(i==1),flag1,flag2&&i==a[pos+1]);
		}
	}
	if(!flag1&&!flag2)dp[pos][x0][x1]=ans;
	return ans;
}
int solve(int n){
	memset(dp,-1,sizeof(dp));
	tot=0;
	while(n){
		a[++tot]=n&1;
		n>>=1;
	}
	reverse(a+1,a+tot+1);
	return dfs(0,0,0,true,true);
}
int main(){
	cin>>x>>y;
	cout<<solve(y)-solve(x-1);
	return 0;
}

10pts
WA on #2 #3 #5 #6 #9 #10
TLE on #4 #7 #8

2023/8/19 16:59
加载中...