首页 > 代码库 > Hdu3652B-number数位dp
Hdu3652B-number数位dp
就是记个余数然后像不要62那样搞
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;typedef long long LL;LL dp[100][100][100];LL up[1111];LL dfs(LL now,LL pre,LL mod,LL flag){ if(now==1&&pre==2&&mod==0) return 1; if(now==1) return 0; if(!flag&&~dp[now][pre][mod]) return dp[now][pre][mod]; LL limit=flag?up[now-1]:9,ret=0; for(LL i = 0 ;i <=limit;i++){ LL pre1;LL mod1;LL flag1; if(pre==1&&i==3) pre1=2; else if(pre==2) pre1=2; else if((pre==0||pre==1)&&i==1) pre1=1; else pre1=0; mod1=(mod*10+i)%13; if(flag&&i==limit) flag1=1; else flag1=0; ret+=dfs(now-1,pre1,mod1,flag1); } return flag? ret: dp[now][pre][mod]=ret;}LL solve(LL x){ LL len=0; while(x){ up[++len]=x%10; x/=10; } return dfs(len+1,0,0,1);}int main(){ LL n; memset(dp,-1,sizeof(dp)); while(cin>>n){ cout<<solve(n)<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。