BZOJ1026 - [SCOI2009]windy数

2016/10/18

一道数位dp的入门题。

之前根本不知道数位dp这个概念(瞎),只要dp是仅与独立的数位相关的,并且满足最优子结构性质就可以做。

题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?

代码

表示长度为i,最高位为j的方案数。

 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
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1E9;
int A, B;
int F[15][10];

void windy() { // 打表
    for(int i=0;i<=9;i++) F[1][i] = 1;
    for(int i=2;i<=10;i++) {
        for(int j=0;j<10;j++) {
            for(int k=0;k<10;k++) {
                if(abs(j-k) >= 2)
                    F[i][j] += F[i-1][k];
            }
        }
    }
}

int calc(int end) {  // 求 [0, end) 中的windy数
    int len = 0, bit[15];
    while(end) {
        bit[++len] = end % 10; end /= 10;
    }

    bit[len+1] = 0;
    int ans = 0;
    for(int i=1;i<len;i++)
        for(int j=1;j<10;j++) ans += F[i][j];
    for(int j=1;j<bit[len];j++) ans += F[len][j];
    for(int i=len-1;i;i--) {
        for(int j=0;j<bit[i];j++) {
            if(abs(j - bit[i+1]) >= 2) ans += F[i][j];
        }
        if(abs(bit[i] - bit[i+1]) < 2) break;
    }

    return ans;
}

int main() {
    cin >> A >> B;
    windy();
    cout << calc(B+1) - calc(A) << endl;
}