```cpp
void solve(){
long long a, b;
cin >> a >> b;
long long dp[20][20][20];
vector<int> num;
function<long long(int, int, int, bool, bool, bool, bool, bool)> dfs = [&](int pos, int pre, int sec_pre, bool lead, bool limit, bool has8, bool has4, bool con)->long long{
// cout << pos << " " << pre << " " << sec_pre << endl;
if (has8 && has4){
return 0;
}
if (pos == 0){
return con;
}
if (limit == false && dp[pos][pre][sec_pre] != -1){
return dp[pos][pre][sec_pre];
}
long long res = 0;
int up = (limit == true ? num[pos] : 9);
for (int i = 0; i <= up; ++i){
if (lead == true && i == 0){
continue;
}
res += dfs(pos - 1, i, pre, false, limit && (i == up), has8 || (i == 8), has4 || (i == 4), con || (i == pre && i == sec_pre));
}
if (!limit){
dp[pos][pre][sec_pre] = res;
}
return res;
};
auto cal = [&](long long x)->long long{
num.resize(1);
while (x){
num.emplace_back(x % 10);
x /= 10;
}
memset(dp, -1, sizeof(dp));
if (int(num.size()) != 12){
return 0;
}
return dfs(int(num.size()) - 1, 0, 0, true, true, false, false, false);
};
cout << cal(b) - cal(a - 1) << '\n';
}
这是过不了的代码，加了3个维度后就可以了
```
by Touris2ts @ 2024-01-15 21:51:17
```cpp
#include <bits/stdc++.h>
using namespace std;
#define dbg std::cout << "----------------------------------------" << std::endl;
constexpr array<long long, 63> pow2_values{1ll,2ll,4ll,8ll,16ll,32ll,64ll,128ll,256ll,512ll,1024ll,2048ll,4096ll,8192ll,16384ll,32768ll,65536ll,131072ll,262144ll,524288ll,1048576ll,2097152ll,4194304ll,
8388608ll,16777216ll,33554432ll,67108864ll,134217728ll,268435456ll,536870912ll,1073741824ll,2147483648ll,4294967296ll,8589934592ll,17179869184ll,34359738368ll,68719476736ll,
137438953472ll,274877906944ll,549755813888ll,1099511627776ll,2199023255552ll,4398046511104ll,8796093022208ll,17592186044416ll,35184372088832ll,70368744177664ll,140737488355328ll,
281474976710656ll,562949953421312ll,1125899906842624ll,2251799813685248ll,4503599627370496ll,9007199254740992ll,18014398509481984ll,36028797018963968ll,72057594037927936ll,
144115188075855872ll,288230376151711744ll,576460752303423488ll,1152921504606846976ll,2305843009213693952ll,4611686018427387904ll
};
constexpr array<int, 4> dx {-1, 1, 0, 0};
constexpr array<int, 4> dy {0, 0, -1, 1};
constexpr array<int, 8> dx2 {-1, -1, 0, 1, 1, 1, 0, -1};
constexpr array<int, 8> dy2 {0, -1, -1, -1, 0, 1, 1, 1};
long long fastPower(long long a, long long b, long long mod = int(1e9 + 7)){long long rst = 1;while (b){if (b & 1){rst = rst * a % mod;}b >>= 1;a = a * a % mod;} return rst;}
inline long long fermatInverse(long long a, long long mod){
return fastPower(a, mod - 2, mod);
}
inline long long lcm(long long a, long long b){return a / __gcd(a, b) * b;}
template<typename T, typename U>
inline bool changeMax(T& a, U b){return a < b ? a = b, true : false;}
template<typename T, typename U>
inline bool changeMin(T& a, U b){return a > b ? a = b, true : false;}
void preProcess(){
}
void solve(){
long long a, b;
cin >> a >> b;
long long dp[20][20][20][2][2][2];
vector<int> num;
function<long long(int, int, int, bool, bool, bool, bool, bool)> dfs = [&](int pos, int pre, int sec_pre, bool lead, bool limit, bool has8, bool has4, bool con)->long long{
// cout << pos << " " << pre << " " << sec_pre << endl;
if (has8 && has4){
return 0;
}
if (pos == 0){
return con;
}
if (limit == false && dp[pos][pre][sec_pre][con][has8][has4] != -1){
return dp[pos][pre][sec_pre][con][has8][has4];
}
long long res = 0;
int up = (limit == true ? num[pos] : 9);
for (int i = 0; i <= up; ++i){
if (lead == true && i == 0){
continue;
}
res += dfs(pos - 1, i, pre, false, limit && (i == up), has8 || (i == 8), has4 || (i == 4), con || (i == pre && i == sec_pre));
}
if (!limit){
dp[pos][pre][sec_pre][con][has8][has4] = res;
}
return res;
};
auto cal = [&](long long x)->long long{
num.resize(1);
while (x){
num.emplace_back(x % 10);
x /= 10;
}
memset(dp, -1, sizeof(dp));
if (int(num.size()) != 12){
return 0;
}
return dfs(int(num.size()) - 1, 0, 0, true, true, false, false, false);
};
cout << cal(b) - cal(a - 1) << '\n';
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
preProcess();
while (tc--){
solve();
}
return 0;
}
```
by Touris2ts @ 2024-01-15 21:51:45
为什么只有pos, pre, pre的pre三个变量作为dp的转移状态不行，还要加上8,4,连续这3个维度呢？如何理解这种差异，求佬发表
by Touris2ts @ 2024-01-15 21:52:42
@[Touris2ts](/user/1180143) 我好像懂了，这么设状态，是因为假如我们的pos一共有11位，现在在第7位。虽然第pos = 8, pre = a, sec_pre =b已经被计算过了，但是第11位是什么，我们不知道，我们必须定义4出现跟8出现的情况才能确保第11位的数字出现，跟我们之前计算过的状态不冲突（也就是说之前计算的状态是可用的），如果之前计算的时候第11位是4，但是现在第11位是2，那么之前计算的状态就失效了。 动态规划的核心是历史计算结果避免重复计算，但是我们现在要利用的结果如果不能保证跟历史计算的结果 状态完全相同，那么这个结果就不能利用了。
by Touris2ts @ 2024-01-15 22:05:28
@[Touris2ts](/user/1180143) 你的理解是正确的，谢谢大佬
by Touris2ts @ 2024-01-15 22:05:41
@[Touris2ts](/user/1180143) 自娱自乐上了
by 7The_shy @ 2024-01-19 11:07:32