首页 > 代码库 > hdu 3652

hdu 3652

2024-11-25 11:33:38   203人阅读

观察区数字是否含有13并且能被13整除

基础的数位dp到此大概就结束了，接下来会练习一些网络赛和区域赛的数位dp进一步巩固

Sample Input

13
100
200
1000

Sample Output
1
1
2
2

注意在判断新状态的时候顺序不能弄反，否则会把之前的正确状态覆盖

 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 //printf("----\n"); 8 using namespace std; 9 int n,m,t;10 int dp[15][3][15];11 int digit[15];12 int dfs(int p,int s,int mod,bool e) {       //s记录上一位,mod记录余数13     printf("%d\n",mod);14     if (p==-1) return s==2&&mod==0;15     if (!e &&dp[p][s][mod]!=-1) return dp[p][s][mod];16     int res = 0;17     int u = e?digit[p]:9;18     for (int i=0;i<=u;++i)19     {20         //printf("%d %d %d\n",p,s,i);21         int ns=s;22         if(s==1&&i!=1)  ns=0;23         if(s==0&&i==1)  ns=1;24         if(s==1&&i==3)  ns=2;25         res+=dfs(p-1,ns,(mod*10+i)%13,e&&i==u); //看是否能整除13，而且由于是从原来数字最高位开始算，事实上这个过程就是一个除法过程26     }27     return e?res:dp[p][s][mod]=res;28 }29 int solve(int n)30 {31     int len=0;32     while(n)33     {34         digit[len++]=n%10;35         n/=10;36     }37     return dfs(len-1,0,0,1);38 }39 int main()40 {41     int i,j,k;42     //freopen("1.in","r",stdin);43     memset(dp,-1,sizeof(dp));44     while(scanf("%d",&n)!=EOF)45     {46         printf("%d\n",solve(n));47     }48 }

 

hdu 3652


联系
我们