学步园

题意:

求1到N之间含有13且能被13整除的数的个数.

思路:

数位DP. 注意求"整除"条件需要记录余数,即模.

#include <cstdio>
#include <cstring>
using namespace std;

int dp[12][15][2][12];
int bit[12];
//pos:处理的位数 num:模13余数 t:是否已有13 e:当前尾数 flag:是否进入上限范围
int dfs(int pos, int num, bool t, int e, bool flag)
{
    if(pos==-1)//从高位向低位已经全部确定了(dfs到了叶子)
        return t&&(!num);//判是否仍满足有13能整除,有,则计数1
    if(!flag && dp[pos][num][t][e]!=-1)//没到上限,并且已经算过,直接输答案
        return dp[pos][num][t][e];
    int end = flag?bit[pos]:9;//该位最大值,若之前的数没到上限,这一位可以取到最大,9.否则就是N的该位
    int ans = 0;
    for(int i=0;i<=end;i++)
    {//向下一位dp,余数如此累加便可(?),是否已有13或者刚刚出现13,尾数,是否此位仍然是上限
        ans += dfs(pos-1, (num*10+i)%13, t||(e==1&&i==3), i, flag&&(i==end));
    }
    if(!flag)   dp[pos][num][t][e] = ans;//如果不是上限,此位可通用,记忆化搜索.
    return ans;
}

int solve(int n)
{
    int pos = 0;
    while(n)
    {
        bit[pos++] = n % 10;
        n /= 10;
    }
    return dfs(pos-1, 0, 0, 0, 1);//最后的flag只是初始化为1保证不影响后续结果.解释的话..还是不需要解释了
}

int main()
{
    int n;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d",&n)==1)
    {
        printf("%d\n",solve(n));
    }
}