大家好！我是小码匠。
本周开始学习数位DP，今天分享的是一道经典的模版题。
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：7道
- 待完成：293道
已完成目标：
分类 | 算法 | 题目 |
|---|---|---|
算法基础 | 前缀和 | 【第001题】题解分享：湖南省选->激光炸弹 |
算法基础 | 差分 | 【第002题】题解分享：P4552 [Poetize6] IncDec Sequence |
算法基础 | 高维前缀和 | 【第003题】题解及代码分享：CodeForces 165E Compatible Numbers |
算法基础 | 尺取 | 【第004题】题解及代码分享：AtCoder ABC326-C |
动态规划 | 动态规划 | 【第005题】题解及代码分享：AtCoder ABC326-D |
算法基础 | 高维前缀和 | 【第006题】题解及代码分享：高位前缀和之AtCoder ARC100 - E Or Plus Max |
动态规划 | 数位DP | 【第007题】题解及代码分享：数位DP经典模版题 [SCOI2009] windy 数 |
前置知识
- 数位DP
- https://oi-wiki.org/dp/number/
题目描述
windy 定义了一种 windy 数。
题目描述
不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数？
输入格式
输入只有一行两个整数，分别表示 a 和 b。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1复制
代码语言：javascript复制1 10
输出 #1复制
代码语言：javascript复制9
输入 #2复制
代码语言：javascript复制25 50
输出 #2复制
代码语言：javascript复制20
说明/提示
数据规模与约定
对于全部的测试点，保证
。
题解
补充样例数据
输入1
代码语言：javascript复制1 9
输出1
代码语言：javascript复制9
输入2
代码语言：javascript复制99 101
输出2
代码语言：javascript复制0
输入3
代码语言：javascript复制1 1
输出3
代码语言：javascript复制1
输入4
代码语言：javascript复制1 300
输出4
代码语言：javascript复制174
输入5
代码语言：javascript复制1 200000
输出5
代码语言：javascript复制46859
思路
- 一道比较经典数位DP模版题，思路大家请参考洛谷官方
- https://www.luogu.com.cn/problem/solution/P2657
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int dp[15][15], a[20], l = 0;
void init() {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i <= 9; i) {
dp[i][1] = 1;
}
for (int i = 2; i <= 10; i) {
for (int j = 0; j <= 9; j) {
for (int k = 0; k <= 9; k) {
if (abs(j - k) >= 2) {
dp[j][i] = dp[k][i - 1];
}
}
}
}
}
int solve(int num) {
int ans = 0;
l = 0;
memset(a, 0, sizeof(a));
while (num > 0) {
a[ l] = num % 10;
num /= 10;
}
for (int i = 1; i <= 9; i) {
for (int j = 1; j < l; j) {
ans = dp[i][j];
}
}
for (int i = 1; i < a[l]; i) {
ans = dp[i][l];
}
for (int j = l - 1; j >= 1; --j) {
for (int i = 0; i < a[j]; i) {
if (abs(i - a[j 1]) >= 2) {
ans = dp[i][j];
}
}
if (abs(a[j] - a[j 1]) < 2) {
break;
}
}
return ans;
}
void best_coder() {
int x, y;
cin >> x >> y;
init();
int ans1 = solve(x);
int ans2 = solve(y 1);
cout << ans2 - ans1;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
END
