Hdu 3652 B-number (同余数位DP)
题目链接：
题目描述：
给出一个数n，问 [1, n]区间内有几个数能被13整除并且还有13这个子串？
解题思路：
能整除的数位DP，确定好状态随便搞搞就能过了。dp[x][mod][y][z] 表示 x位的整数，mod 13 等于几， y表示是否出现过13， 最后一位是z。
还有就是发现记忆化搜索 + 数位dp写出来真的很美讷。不说了，直接上代码，干净粗暴。
#include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 15; int dp[maxn][maxn][maxn][maxn], bit[maxn]; int dfs (int pos, int mod, bool s, int num, bool flag) { if (pos == -1) //每个位置都满了 return mod==0 && s; //满足题意返回true //对于flag==1的时候，还是要向下搜索的，直接返回可能会加多 if (!flag && dp[pos][mod][s][num] != -1) return dp[pos][mod][s][num]; //如果前面的数都是等于n的，辣么当前这位也不能大于bit[pos] int len = flag?bit[pos]:9; int ans = 0; for (int i=0; i<=len; i++) ans += dfs (pos-1, (mod*10+i)%13, s||(num==1&&i==3), i, flag&&(i==len)); if (!flag) dp[pos][mod][s][num] = 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); } int main () { int n; memset (dp, -1, sizeof(dp)); while (scanf ("%d", &n) != EOF) printf ("%d ", solve (n)); return 0; }