数位DP一般有两种思路
正向：利用公式化的DP关系从低位往高位递推
逆向：记忆化搜索
其中需要注意的是：记忆化搜索时的dp更新，往往会一不小心犯错，例如
for (top = 1; top<= nf; ++top) { memset(dp, -1, sizeof dp); res += dfs(0, top, 0, 0, top==nf); }如果是按高到低位分别计算，一般需要将dp清空
hdu 4933 Miaomiao's Function
该题考点确实变态，借鉴了别人的思路。dp[i][2]表示：i当前位数（起始位非0），数的总个数&满足题意（从高到低位，奇数位和减去偶数位和）所有数计算结果的和因为位数不同从而导致奇偶判别不同，所以需要按从高到低位分别计算。import java.math.BigInteger; import java.util.Scanner; class node { public BigInteger s = BigInteger.ZERO, n = BigInteger.ZERO; } public class Main { public static final int MAXN = 105; public static Scanner in = null; public static int[] fez = new int[MAXN]; public static node[] dp = new node[MAXN]; public static int top; public static node dfs(int dx, boolean flg) { node res = new node(); if (dx == 0) { res.n = BigInteger.ONE; return res; } if (!flg && !dp[dx].n.equals(BigInteger.ZERO)) return dp[dx]; int bg = dx == top ? 1 : 0, ed = flg ? fez[dx] : 9; for (int i = bg; i <= ed; ++i) { node p = dfs(dx - 1, flg && fez[dx] == i); res.n = res.n.add(p.n); res.s = res.s.add(p.s); if ((top - dx) % 2 == 1) res.s = res.s.add(p.n.multiply(BigInteger.valueOf(-i))); else res.s = res.s.add(p.n.multiply(BigInteger.valueOf(i))); } if (!flg) dp[dx] = res; return res; } public static BigInteger ff(BigInteger x) { if (x.equals(BigInteger.ZERO)) return x; if (x.compareTo(BigInteger.valueOf(0)) < 0) if (x.mod(BigInteger.valueOf(9)).equals((BigInteger.valueOf(0)))) return (BigInteger.valueOf(9)); else return x.mod(BigInteger.valueOf(9)); if (x.mod(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) return BigInteger.valueOf(9); else return x.mod(BigInteger.valueOf(9)); } public static BigInteger qq(BigInteger x) { BigInteger res = BigInteger.ZERO; if (x.equals(BigInteger.ZERO) || x.equals(BigInteger.valueOf(-1))) return res; int fn = 0; while (!x.equals(BigInteger.ZERO)) { ++fn; fez[fn] = x.mod(BigInteger.valueOf(10)).intValue(); x = x.divide(BigInteger.valueOf(10)); } for (top = 1; top <= fn; ++top) { for (int i = 1; i <= 104; ++i) { dp[i] = new node(); dp[i].s = BigInteger.ZERO; dp[i].n = BigInteger.ZERO; } res = res.add(dfs(top, top == fn).s); } return res; } static { in = new java.util.Scanner(System.in); } public static void main(String[] args) { int t = in.nextInt(); while (t-- != 0) { BigInteger L = in.nextBigInteger(), R = in.nextBigInteger(); BigInteger res = qq(R).add(qq(L.add(BigInteger.valueOf(-1))).negate()); BigInteger p = ff(res); if (p.equals(BigInteger.ZERO)) System.out.println("Error!"); else System.out.println(res.mod(p).add(p).mod(p)); } } }
hdu 2089 不要62
dp[i][j]：i位且以j为开头，满足题意的数的个数#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int dp[10][10], fenz[10], nf, top, sm[10]; int L, R; void m_init() { for (int i = 0; i< 10; ++i) dp[1][i] = 1; dp[1][4] = 0; for (int i = 1; i<6; ++i) { for (int k = 0; k< 10; ++k) { if (k == 4) continue; for (int j = 0; j< 10; ++j) { if (k==2 && j == 6 || j==4) continue; dp[i+1][j] += dp[i][k]; } } } sm[0] = 0; for (int i = 1; i<7; ++i) { for (int j = 1; j< 10; ++j) sm[i] += dp[i][j]; } } int dfs(int dx, int flg, bool six) { int res = 0; if (dx == 0) return 1; if (!flg) return sm[dx]; int bg = dx==top?1:0, ed = flg?fenz[dx]:9; for (int i = bg; i<= ed; ++i) { if (i == 4) continue; if (six && i==2 ) continue; if (flg && i==ed) res += dfs(dx-1, 1, i==6); else res+=dp[dx][i]; } return res; } int solve(int x) { if (x < 0) return 0; int res = 1; if (x == 1000000) ++res, --x; nf = 0; while(x) { ++nf; fenz[nf] = x%10; x /= 10; } for (top = 1; top<= nf; ++top) { res += dfs(top, top==nf, 0); } return res; } void test() { for (int i = 0; i<= 100; ++i) { printf("%d : %d\n", i, solve(i)); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif // ONLINE_JUDGE m_init(); // test(); while (scanf("%d%d", &L, &R)!=EOF && (L+R)) { printf("%d\n", solve(R)-solve(L-1)); } return 0; }
hdu 4389 X mod f(x)
dp[i][j][k][o]：i位，前缀的数位和为j，mod（k），余数为o#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int dp[10][82][82][82]; int L, R; int fenz[10], nf; int dfs(int dx, int sm, int mod, int yy, int flg) { if (sm > mod) return 0; if (dx == 0) return sm==mod&&yy==0; if (!flg && dp[dx][sm][mod][yy]!=-1) return dp[dx][sm][mod][yy]; int ed = flg?fenz[dx]:9, res = 0; for (int i = 0; i<= ed; ++i) { res += dfs(dx-1, sm+i, mod, (yy*10+i)%mod, flg&&i==ed); } return flg?res:dp[dx][sm][mod][yy]=res; } int solve(int x) { if (x <= 0) return 0; int res = 0; if (x == 1000000000) ++res, x--; nf = 0; while(x) { fenz[++nf] =x%10; x/=10; } for (int i = 1; i<= nf*9; ++i) { res += dfs(nf, 0, i, 0, 1); } return res; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif // ONLINE_JUDGE int t, cs = 0; scanf("%d", &t); memset(dp, -1, sizeof dp); while (t--) { printf("Case %d: ", ++cs); scanf("%d%d", &L, &R); printf("%d\n", solve(R)-solve(L-1)); } return 0; }
hdu 3709 Balanced Number
大致同上
hdu 3652 B-number
dp[i][j][k][o]：i标识前缀是否含有13，j位数，前一位数位k，前缀mod 13的余数#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 LL; int dp[2][10][10][15]; const int mod = 13; // dp:is have 13, index, pre number, mod 13 int L; int top, nf, fenz[20]; int dfs(int ishv, int dx, int pre, int m, bool flg) { if (dx == 0) return ishv&&m==0; if (!flg && dp[ishv][dx][pre][m]!=-1) return dp[ishv][dx][pre][m]; int bg = 0, ed = flg?fenz[dx]:9; int res = 0, p; for (int i = bg; i<= ed; ++i) { p = ishv || (pre==1&&i==3); res += dfs(p, dx-1, i, (m*10+i)%mod, flg&&i==ed); } return flg?res:dp[ishv][dx][pre][m]=res; } int solve(int x) { nf = 0; while(x) { fenz[++nf] =x%10; x/=10; } return dfs(0, nf, 0, 0, 1); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE memset(dp, -1, sizeof dp); while (scanf("%d", &L)!=EOF) printf("%d\n", solve(L)); return 0; }