Windy 数

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1187 字

求[A,B]中相邻两个数字之差至少为2且不含

一本通
例

正文

/*
原题：Windy 数（一本通 5.3 例 3，SCOI 2009）
题意：求 [A,B] 中相邻两个数字之差至少为 2 且不含前导零的正整数个数。
思路：数位 DP，state=(pos,last,started,tight)。
     首位（未开始时放的首个非 0 数字）无前驱约束；之后每位需满足 |d-last| >= 2。
     答案 = f(B) - f(A-1)。
复杂度：时间 O(log10 B * 10)，空间 O(log10 B * 10)
易错点：单数字本身是 Windy 数（无相邻位）；前导零不计入“数字”。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dig[15];
ll memo[15][10][2][2];
int len;
ll dfs(int pos, int last, bool started, bool tight){
    if(pos == len){
        return started ? 1 : 0;
    }
    if(memo[pos][last][started][tight] != -1) return memo[pos][last][started][tight];
    ll ans = 0;
    int up = tight ? dig[pos] : 9;
    for(int d = 0; d <= up; d++){
        if(started && abs(d - last) < 2) continue;
        ans += dfs(pos + 1, d, started || d != 0, tight && d == up);
    }
    return memo[pos][last][started][tight] = ans;
}
ll f(ll n){
    len = 0;
    ll t = n;
    while(t){
        dig[len++] = t % 10;
        t /= 10;
    }
    if(len == 0) dig[len++] = 0;
    reverse(dig, dig + len);
    memset(memo, -1, sizeof(memo));
    return dfs(0, 0, false, true);
}
int main(){
    ll A, B;
    cin >> A >> B;
    cout << f(B) - f(A - 1) << "\n";
    return 0;
}

Windy 数

正文

一本通·提高篇的其它内容