[SCOI2009] windy 數(shù)

題目背景

windy 定義了一種 windy 數(shù)。

題目描述

不含前導(dǎo)零且相鄰兩個(gè)數(shù)字之差至少為 $2$ 的正整數(shù)被稱為 windy 數(shù)。windy 想知道，在 $a$ 和 $b$ 之間，包括 $a$ 和 $b$ ，總共有多少個(gè) windy 數(shù)？

輸入格式

輸入只有一行兩個(gè)整數(shù)，分別表示 $a$ 和 $b$。

輸出格式

輸出一行一個(gè)整數(shù)表示答案。

樣例 #1

樣例輸入 #1

1 10

樣例輸出 #1

9

樣例 #2

樣例輸入 #2

25 50

樣例輸出 #2

20

數(shù)據(jù)規(guī)模與約定

對(duì)于全部的測(cè)試點(diǎn)，保證 $1\le a\le b\le 2\times 10^9$。

原題

洛谷P2657——傳送門

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int mod = 2e9 + 6; // 本題無用，僅是因?yàn)閼械脛h（）int dp[20][20], a[20];                             // dp記錄[pos][pre_num]狀態(tài)下的滿足條件的個(gè)數(shù)，a[]記錄數(shù)字串
int dfs(int pos, int pre_num, bool bound, bool st) // pos為此時(shí)的位置，pre_num為上一位的數(shù)字，bound表示前面每一位是否都是上界，st表示是否前面全是0
{if (pos == 0) // 枚舉完每一位時(shí)返回return 1;if (!bound && dp[pos][pre_num] != -1) // 不是位于上界，就可以利用前面dfs已經(jīng)求出的答案（！=-1表示前面已經(jīng)求出該答案）return dp[pos][pre_num];int max_num; // 可枚舉的該位的數(shù)的上界if (bound)max_num = a[pos];elsemax_num = 9;int res = 0; // 統(tǒng)計(jì)此時(shí)的答案for (int i = 0; i <= max_num; i++){if (abs(i - pre_num) >= 2){if (st && i == 0) // 如果前面全是0并且該位也是0，那么pre_num依舊設(shè)置為-6，表示后面接任意數(shù)字都不受“相鄰兩個(gè)數(shù)字之差至少為2”這個(gè)限制res = (res + dfs(pos - 1, -6, bound && (i == a[pos]), 1)) % mod;elseres = (res + dfs(pos - 1, i, bound && (i == a[pos]), 0)) % mod;}}if (!bound && !st) // 沒在邊界時(shí)，記錄下該狀態(tài)對(duì)應(yīng)的答案dp[pos][pre_num] = res;return res;
}
int solve(int x)
{memset(dp, -1, sizeof(dp)); // 將dp數(shù)組初始化為-1，表示對(duì)應(yīng)狀態(tài)的答案目前還未計(jì)算出int len = 0;                // 數(shù)字長(zhǎng)度while (x){a[++len] = x % 10;x /= 10;}return dfs(len, -6, 1, 1); // pre_num設(shè)置為-6，表示后面接任意數(shù)字都不受“相鄰兩個(gè)數(shù)字之差至少為2”這個(gè)限制
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int a, b;cin >> a >> b;cout << solve(b) - solve(a - 1); // ans[a,b]即為ans[0,b]-ans[0,a-1]return 0;
}