首页 > 代码库 > [数位dp] hdu 3271 SNIBB
[数位dp] hdu 3271 SNIBB
题意:有两种询问:
q=1,在[x,y]区间内,转换成b进制数,数位和为m的有多少个。
q=2,在[x,y]区间内,转换成b进制数,数位和是m的第k个数是多少(十进制),不存在按题目给出输出。
思路:
和普通数位dp一样,第几个数的话就是二分判断。
然后就是按常理要开4维,就是dp[i][sum][b][m] i位,和为sum,b进制,最后和为m
但是开不下,所以开3维每次初始化。
注意一下:
1、每次都要初始化
2、x不一定小于y
3、是[x,y]不是(x,y]
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"stack" #include"algorithm" #include"iostream" using namespace std; __int64 dp[33][320][65],num[33]; // i位 和是sum 进制b 的关于m的答案 但是再替m开一维开不下,所以不能在外面初始化 __int64 dfs(__int64 site,__int64 sum,__int64 b,int f,__int64 m) { if(site==0) return sum==m?1:0; if(!f&&dp[site][sum][b]!=-1) return dp[site][sum][b]; __int64 len=f?num[site]:b-1; __int64 ans=0; for(__int64 i=0; i<=len; i++) { ans+=dfs(site-1,sum+i,b,f&&i==len,m); } if(!f) dp[site][sum][b]=ans; return ans; } __int64 solve(__int64 x,__int64 b,__int64 m) { int cnt=0; if(x<0) return 0; while(x) { num[++cnt]=x%b; x/=b; } return dfs(cnt,0,b,1,m); } int main() { int cas=1; int q; while(scanf("%d",&q)!=-1) { __int64 x,y,b,m,k; memset(dp,-1,sizeof(dp)); //必须放里面 printf("Case %d:\n",cas++); if(q==1) { scanf("%I64d%I64d%I64d%I64d",&x,&y,&b,&m); if(x>y) swap(x,y); printf("%I64d\n",solve(y,b,m)-solve(x-1,b,m)); } else { scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&b,&m,&k); x--; //注意这里是求 [x,y]区间内的! if(x>y) swap(x,y); __int64 ans=-1,s; s=solve(x,b,m); s+=k; __int64 l=x+1,r=y; while(l<=r) { __int64 mid=(l+r)/2; if(solve(mid,b,m)>=s) { ans=mid; r=mid-1; } else l=mid+1; } if(ans!=-1) printf("%I64d\n",ans); else puts("Could not find the Number!"); } } return 0; }
[数位dp] hdu 3271 SNIBB
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。