題目鏈接：點(diǎn)擊查看

題目大意：規(guī)定一個數(shù)如果二進(jìn)制中0的個數(shù)大于等于1的個數(shù)，則這個數(shù)稱為“整數(shù)”，問閉區(qū)間a，b中有多少個整數(shù)

題目分析：數(shù)位dp，dp[pos][c0][c1]代表前pos為中有c0個0和c1個1的整數(shù)數(shù)量

pos：當(dāng)前位置，c0:0的個數(shù)，c1:1的個數(shù)，lead：是否有前導(dǎo)零，limit：是否為最高位

注意：對前導(dǎo)零的判斷

上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=30;LL dp[50][50][50];int b[N];LL dfs(int pos,int c0,int c1,bool lead,bool limit) {if(pos==-1){if(c0>=c1)return 1;elsereturn 0;}if(!limit&&!lead&&dp[pos][c0][c1]!=-1)//如果有前導(dǎo)零，則涉及到數(shù)位問題，需要重新循環(huán)求解return dp[pos][c0][c1];int up=limit?b[pos]:1;LL ans=0;for(int i=0;i<=up;i++){if(lead&&i==0)//包含前導(dǎo)零ans+=dfs(pos-1,0,0,true,limit&&i==b[pos]);else if(i)ans+=dfs(pos-1,c0,c1+1,false,limit&&i==b[pos]);elseans+=dfs(pos-1,c0+1,c1,false,limit&&i==b[pos]);}if(!limit&&!lead)//若沒有前導(dǎo)零也不是最高位，可以存下來反復(fù)使用dp[pos][c0][c1]=ans;return ans; }LL solve(LL n) {int cnt=0;while(n){b[cnt++]=n&1;n>>=1;}return dfs(cnt-1,0,0,true,true); }int main() { // freopen("input.txt","r",stdin);LL a,b;memset(dp,-1,sizeof(dp));while(cin>>a>>b){cout<<solve(b)-solve(a-1)<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 3252 Round Numbers(数位dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。