首页 > 代码库 > [数位dp] hdu 5106 Bits Problem
[数位dp] hdu 5106 Bits Problem
题意:
给一个N和一个R(用二进制表示)
问 [0,R)二进制中含有N个1的数之和
样例 1 1000
答案为 1+2+4=7
思路:
数位dp[1002][1002]第几位含有几个1
然后需要存的有两东西一个是有多少个数,以及和是多少
接着转移的时候 就是状态的sum=这个site的位权*之后含有的个数+之后的和
记得个数和和都要取模,一开始个数忘记取模了 %>_<%
然后需要优化 当当前1的个数已经超过sum了 直接返回0个数和是0
然后清空数组的时候只需要清空 1000*N个空间 (1000*1000就超时了。。。)
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"map" #include"vector" #include"string" #define inf 0x7fffffff #include"iostream" #define ll __int64 using namespace std; ll mod=1000000007; struct node { ll cnt,sum; node() { cnt=-1; sum=0; } } dp[1005][1005]; int num[1234]; ll bit[1234]; char v[1234]; int k; node dfs(int site,int sum,int f) { if(sum>k) { node tep; tep.cnt=0; return tep; } if(site==0) { node tep; if(sum==k) { tep.cnt=1; tep.sum=0; } else { tep.cnt=0; tep.sum=0; } return tep; } if(!f&&dp[site][sum].cnt!=-1) return dp[site][sum]; int len=f?num[site]:1; node ans; ans.cnt=0; for(int i=0; i<=len; i++) { node tep; if(i==0) tep=dfs(site-1,sum,f&&i==len); else tep=dfs(site-1,sum+1,f&&i==len); ans.cnt+=tep.cnt; if(ans.cnt>=mod) ans.cnt%=mod; ll sss; if(i==0) sss=0; else sss=bit[site]; ans.sum+=(tep.cnt*sss)%mod+tep.sum; if(ans.sum>=mod) ans.sum%=mod; } if(!f) dp[site][sum]=ans; return ans; } int main() { bit[1]=1; for(int i=2; i<=1000; i++) bit[i]=(bit[i-1]*2)%mod; while(scanf("%d%s",&k,v)!=-1) { memset(num,0,sizeof(num)); for(int i=0;i<=1000;i++) { for(int j=0;j<=k;j++) { dp[i][j].cnt=-1; dp[i][j].sum=0; } } if(k==0) { puts("0"); continue; } int len=strlen(v); for(int i=0; v[i]; i++) num[i+1]=v[len-1-i]-'0'; int i=1; while(1) //记得减一 { if(num[i]==1) { num[i]=0; break; } else { num[i]=1; num[i+1]--; if (num[i+1]==0) break; i++; } } if (num[len]==0) len--; node ans; ans=dfs(len,0,1); printf("%I64d\n",ans.sum%mod); } return 0; }
[数位dp] hdu 5106 Bits Problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。