原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3652
题意：求1-n内包含13且被13整除的数的个数。
题解：很明确的数位DP，之前在纠结这个整除13怎么处理，实际上只需记录当前%13的余数，最后答案在%13==0的里面找。
have的含义：0—未有13且此位不为1，1—未有13且此位为1，2—已有13.
这里记忆化的内容实际上是从当前位置(从len开始)当前状态到位置(0)的目标状态的方案数，因此可以在每一次的n重复利用。
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int n;
int up[15];
LL dp[15][14][5];
int len;
LL dfs(int pos,int mod,int have,int lim) //pos，lim是当前位，此处计算的也是当位，mod，have 都是截止到上一位为止
{
if(pos==0) return (long long)(have==2&&mod==0);
if(!lim&&dp[pos][mod][have]!=-1) return dp[pos][mod][have];
int tp=lim?up[pos]:9;
LL ans=0;
for(int i=0;i<=tp;i++)
{
int modd,havv,limm;
modd=((mod*10)%13+i)%13;
if(have==0)
{
if(i==1) havv=1;
else havv=0;
}
if(have==1)
{
if(i==1) havv=1;
else if(i==3) havv=2;
else havv=0;
}
if(have==2) havv=2;
if(lim&&i==up[pos]) limm=1; else limm=0;
ans+=dfs(pos-1,modd,havv,limm);
}
if(!lim) return dp[pos][mod][have]=ans;
else return ans;
}
int main()
{
memset(dp,-1,sizeof(dp));
while(scanf("%d",&n)!=EOF)
{
len=0;
while(n) {up[++len]=n%10;n=n/10;}
printf("%lld\n",dfs(len,0,0,1));
}
return 0;
}