动态规划学习系列——数位DP（练手三）

题目链接：HDU 3652

解题思路：
数位DP，状态 dp[i][j][k][c]表示 i 位数中，以 j 开头的，模13为k的数的统计情况，其中 c 可取0或者1，0表示不包含13，1表示包含，这样我们就可以把所有的数分成两部分，设计状态转移方程。
1、状态转移方程：

dp[i][j][(tmp*j+l)%13][1]+=dp[i-1][k][l][1];
if(j==1&&k==3)      // 出现13的前缀，把0的部分放进1里面
 dp[i][j][(tmp*j+l)%13][1]+=dp[i-1][k][l][0];
else                // 没有出现，把0的部分加进来
 dp[i][j][(tmp*j+l)%13][0]+=dp[i-1][k][l][0];

DP过程之后，我们就可以得到一个完备的dp数组，包含着所有需要的数位统计信息，之后进行统计整合。
2、统计：
主要过程还是按照传统的数位DP那么写，同时在DP过程中需要记录前缀的信息( pre )，通过判断前缀，决定是否将把后缀不包含13的数字放进最终答案里。

AC代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n,dp[20][10][15][2],ans,num[20],cnt=0;

void cal(int n)
{
int tmp=n;
    cnt=0;
while(tmp)
    {
        num[cnt++]=tmp%10;
        tmp/=10;
    }
}

int main()
{
while(~scanf("%d",&n))
    {
memset(num,0,sizeof(num));
memset(dp,0,sizeof(dp));
        n++,ans=0,cal(n);

for(int i=0;i<10;i++)
            dp[0][i][i%13][0]=1;

int tmp=1;
for(int i=1;i<cnt;i++)
        {
            tmp*=10;
for(int j=0;j<10;j++)
            {
for(int k=0;k<10;k++)
                {
for(int l=0;l<13;l++)
                    {
                        dp[i][j][(tmp*j+l)%13][1]+=dp[i-1][k][l][1];
if(j==1&&k==3)
                            dp[i][j][(tmp*j+l)%13][1]+=dp[i-1][k][l][0];
else
                            dp[i][j][(tmp*j+l)%13][0]+=dp[i-1][k][l][0];
                    }
                }
            }
        }

int sum=int(pow(10,cnt-1)+0.5),flag=0,pre=0;
for(int i=cnt-1;i>=0;i--)
        {
for(int j=0;j<num[i];j++)
            {
for(int k=0;k<13;k++)
                {
int tmp=(pre+k)%13;
if(tmp==0)
                    {
                        ans+=dp[i][j][k][1];
if(flag)
                            ans+=dp[i][j][k][0];
else if(num[i+1]==1&&j==3)
                            ans+=dp[i][j][k][0];
                    }
                }
            }
if(num[i+1]==1&&num[i]==3)
                flag=1;
            pre+=sum*num[i],sum/=10;
        }

printf("%d\n",ans);
    }

return 0;
}

总结：
注意状态设计+细节处理。