数位DP
题目描述:
计算[l, r]中不含数字62且不包含数字4的数的总个数
状态定义:
f[i][j]表示共有 i 位,且最高位为 j 的合法方案数
假设 k 为 j 后面的数字,则状态转移:
Code
#include <iostream>
#include <cstring>
#include <vector>
const int N = 15;
int f[N][10];
void init() {
for (int i = 0; i <= 9; i ++ )
if (i != 4) f[1][i] = 1;
for (int i = 2; i < N; i ++ )
for (int j = 0; j <= 9; j ++ ) {
if (j == 4) continue; // 不合法状态直接continue
for (int k = 0; k <= 9; k ++ ) {
if (k == 4 || j == 6 && k == 2) continue;
f[i][j] += f[i - 1][k];
}
}
}
int cal(int n) {
if (!n) return 1;
std::vector<int> nums;
while (n) nums.emplace_back(n % 10), n /= 10;
int res = 0, pre = 0;
for (int i = nums.size() - 1; i >= 0; i -- ) {
int x = nums[i];
for (int j = 0; j < x; j ++ ) {
if (j == 4 || pre == 6 && j == 2) continue;
res += f[i + 1][j];
}
if (x == 4 || pre == 6 && x == 2) break; // 说明不存在右分支,直接break
pre = x;
if (!i) res ++ ;
}
return res;
}
int main() {
init();
int l, r;
while (std::cin >> l >> r, l || r)
std::cout << cal(r) - cal(l - 1) << '\n';
return 0;
}
记忆化搜索
#include <iostream>
#include <cstring>
const int N = 15;
int a[N];
int f[N][N];
// pos:当前第几位
// pre:上一位是几
// limit:当前位是否有限制
int dfs(int pos, int pre, bool limit) {
if (!pos) return 1;
if (!limit && ~f[pos][pre]) return f[pos][pre];
int res = 0, up = limit ? a[pos] : 9;
for (int i = 0; i <= up; i ++ ) {
if (i == 4 || pre == 6 && i == 2) continue;
res += dfs(pos - 1, i, limit && i == up);
}
return limit ? res : f[pos][pre] = res;
}
int cal(int n) {
memset(f, -1, sizeof f);
int len = 0;
while (n) a[++ len] = n % 10, n /= 10;
return dfs(len, 0, 1);
}
int main() {
int l, r;
while (std::cin >> l >> r, l || r)
std::cout << cal(r) - cal(l - 1) << '\n';
return 0;
}
标签:pre,不要,int,res,pos,62,include
From: https://www.cnblogs.com/zjh-zjh/p/16711252.html