user
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 没有连续三位数字的和超过给定值的数
有多少个20位数字n（不包括前导0）满足，不存在连续三位数字的和超过9？
我的思路:dp.
设dp[l][i][j][k]为长度为l的,当前所填位数为i,上一位为j,上上一位为k的所有数的情况.
直接转移即可.
初始情况:
dp[1][0~9][0][0]=1
答案:
dp[20][1~9][all][all]
请给我c++代码实现,你可能需要int128
|
gpt
1
2
3
4
5
6
7
8
9
| 你的思路是**完全正确的**，而且这是一个非常标准的「带历史状态的数位 DP」。
下面我给你一份**干净、可直接编译的 C++ 实现**，使用 `__int128` 存储答案，并且逻辑上与你的 DP 定义**等价但稍微简化**，方便实现。
---
## 状态设计（等价但更清晰）
我们定义：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 含义是：
* 已经填了 `pos` 位
* 最近一位是 `last`
* 倒数第二位是 `last2`
* 满足「任意连续三位数字之和 ≤ 9」
`pos ∈ [1, 20]`
`last, last2 ∈ [0, 9]`
### 关键点
* **前导 0 不允许** → 第 1 位只能是 `1~9`
* 当 `pos < 3` 时，不检查三位和
* 当 `pos ≥ 3` 时，要求 `new + last + last2 ≤ 9`
---
## C++ 实现（使用 __int128）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
i128 dp[21][10][10];
int main() {
for (int d = 1; d <= 9; d++) {
dp[1][d][0] = 1;
}
for (int pos = 1; pos < 20; pos++) {
for (int last = 0; last <= 9; last++) {
for (int last2 = 0; last2 <= 9; last2++) {
i128 cur = dp[pos][last][last2];
if (cur == 0) continue;
for (int d = 0; d <= 9; d++) {
if (pos >= 2 && d + last + last2 > 9) continue;
dp[pos + 1][d][last] += cur;
}
}
}
}
i128 ans = 0;
for (int last = 0; last <= 9; last++) {
for (int last2 = 0; last2 <= 9; last2++) {
ans += dp[20][last][last2];
}
}
string s;
while (ans > 0) {
s.push_back('0' + ans % 10);
ans /= 10;
}
if (s.empty()) s = "0";
reverse(s.begin(), s.end());
cout << s << '\n';
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| ---
## 复杂度分析
* 状态数：`20 × 10 × 10 = 2000`
* 转移：每个状态尝试 10 个数字
* 时间复杂度：**O(20 × 10³)**，极小
* 空间复杂度：**O(20 × 10²)**
---
## 小结
✔ DP 设计正确
✔ `__int128` 使用合理
✔ 无前导零处理正确
✔ 连续三位约束精确
如果你愿意，下一步我可以帮你：
* 用 **矩阵快速幂** 做推广（比如 1000 位）
* 改成 **自动机 + DP**
* 或推广为「连续 k 位之和 ≤ S」
你这个题本身已经是竞赛级别思路了 👍
|
fun fact
gpt好像把最后两位数字压到一起了,因为加和小于9,所以直接用一个9存储也是可以的.
一发过,正常现象.
似乎带点”算法”的题目在欧拉计划的难度都虚高,以后要看过题数决定题目真的难不难.
