/*
数位dp,记忆化搜索写法
注意memset(dp,-1,sizeof(dp))是放在外面的,这样保证每次搜索时存的值满足下一次也可以用;
如果放在里面就会超时
每个长度有10000种状态
*/
#include<stdio.h>
#include<string.h>
#define N 20
int len,digit[N],dp[N][10000];
int dfs(int len,int cnt,int ok) {
if(cnt<0)return 0;
if(!len)return 1;
if(!ok&&dp[len][cnt]!=-1)
return dp[len][cnt];
int ans=0,i,maxx=ok?digit[len]:9;
for(i=0;i<=maxx;i++)
ans+=dfs(len-1,cnt-i*(1<<(len-1)),ok&&i==maxx);//
if(!ok)//只有当不是边界时才可以存储
dp[len][cnt]=ans;//长度为len时小于等于cnt的值
return ans;
}
int f(int n,int kk) {
int len=0;
while(n) {
digit[++len]=n%10;
n/=10;
}
return dfs(len,kk,1);
}
int main() {
int t,n,m,k=0,z,kk;
scanf("%d",&t);
memset(dp,-1,sizeof(dp));
while(t--) {
scanf("%d%d",&n,&m);
kk=0;z=1;
while(n) {
kk+=n%10*z;
z*=2;
n/=10;
}
printf("Case #%d: %d\n",++k,f(m,kk));
}
return 0;}
hdu 4734 数位dp
/*数位dp,记忆化搜索写法注意memset(dp,-1,sizeof(dp))是放在外面的,这样保证每次搜索时存的值满足下一次也可以用;如果放在里面就会超时每个长度有10000种状态*/#include<stdio.h>#include<string.h>#define N20int len,digit[N],dp[N][10000];in...
·
转载于:https://www.cnblogs.com/thefirstfeeling/p/4410593.html
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献17条内容
所有评论(0)