首页 > 代码库 > 数位dp模板 [dp][数位dp]
数位dp模板 [dp][数位dp]
现在才想到要学数位dp,我是不是很弱
答案是肯定的
以一道自己瞎掰的题为模板
1 //题: 2 //输入数字n 3 //从0枚举到n,计算这n+1个数中含有两位数a的数的个数 4 //如12930含有两位数93 5 #include<cstdio> 6 #include<cstring> 7 #include<iostream> 8 using namespace std; 9 10 int n,m=0,a,g1,g2;11 int dp[10][10][2],lim[10];12 13 void init(){14 scanf("%d%d",&n,&a);15 g1=a/10; g2=a%10;16 int nn=n;while(nn){17 lim[++m]=nn%10;18 nn/=10;19 }20 }21 22 int dfs(int pos,int pre,bool status,bool limit){23 printf("dfs(%d,%d,%d,%d)\n",pos,pre,status,limit);24 if(pos<1) return status;25 //已找到答案的嘿嘿嘿 26 if(!limit&&dp[pos][pre][status]!=-1) return dp[pos][pre][status];27 28 int end=limit?lim[pos]:9;29 int ret=0;30 31 for(int i=0;i<=end;i++)32 ret+=dfs(pos-1,i,status||(pre==g1&&i==g2),limit&&(i==end));33 34 //没有限制才能记录答案 35 return limit?dp[pos][pre][status]=ret:ret;36 }37 38 int main(){39 init();40 memset(dp,-1,sizeof dp);41 printf("%d\n",dfs(m,0,0,1));42 return 0;43 }
数位dp模板 [dp][数位dp]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。