首页 > 代码库 > 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;}