数位dp模板 [dp][数位dp]

现在才想到要学数位dp,我是不是很弱

答案是肯定的

以一道自己瞎掰的题为模板

 //题:
//输入数字n
//从0枚举到n,计算这n+1个数中含有两位数a的数的个数
//如12930含有两位数93
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; int n,m=,a,g1,g2;
int dp[][][],lim[]; void init(){
scanf("%d%d",&n,&a);
g1=a/; g2=a%;
int nn=n;while(nn){
lim[++m]=nn%;
nn/=;
}
} int dfs(int pos,int pre,bool status,bool limit){
printf("dfs(%d,%d,%d,%d)\n",pos,pre,status,limit);
if(pos<) return status;
//已找到答案的嘿嘿嘿
if(!limit&&dp[pos][pre][status]!=-) return dp[pos][pre][status]; int end=limit?lim[pos]:;
int ret=; for(int i=;i<=end;i++)
ret+=dfs(pos-,i,status||(pre==g1&&i==g2),limit&&(i==end)); //没有限制才能记录答案
return limit?dp[pos][pre][status]=ret:ret;
} int main(){
init();
memset(dp,-,sizeof dp);
printf("%d\n",dfs(m,,,));
return ;
}
上一篇:Numpy Study 2----* dot multiply区别


下一篇:原生js实现一个DIV的碰撞反弹运动,并且添加重力效果