BZOJ1026【SCOI2009】Windy数 <数位DP>

Posted on Symbols count in article: 422 Reading time ≈ 2 mins.

Problem

【SCOI2009】windy数

Time  Limit:  1  Sec\mathrm{Time\;Limit:\;1\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

windywindy定义了一种windywindy数。不含前导零且相邻两个数字之差至少为22的正整数被称为windywindy数。 windywindy想知道，在AA和BB之间，包括AA和BB，总共有多少个windywindy数？

Input

包含两个整数，A,BA,B。

Output

一个整数

Sample Input

输入样例一

1
1 10

输入样例二

1
25 50

Sample Output

输出样例一

1
9

输出样例二

1
20

HINT

数据规模和约定
100%100\%的数据，满足 1≤A≤B≤2×1091\le A \le B \le 2\times 10^9 。

标签：数位DP

Solution

非常经典的一道数位DPDP题。
也是多少OIerOIer数位DPDP入门的第一题啊…

先预处理出DPDP数组，其中f[i][j]f[i][j]从左往右第ii位为jj的windywindy数的个数。
对于询问，分别计算[1,A−1][1, A-1]和[1,B][1, B]中的windywindy数的个数，即在预处理的表中按位查询，统计答案后相减即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
using namespace std;
int f[15][15];
int abs(int x) {return x >= 0 ? x : -x;}
int calc(int x) {
    int len = 0, n[15], t = x, ret = 0;	while (t)	n[++len] = t%10, t /= 10;
    for (int i = 1; i < len; i++)	for (int j = 1; j <= 9; j++)	ret += f[i][j];
    for (int i = len; i; i--) {
        for (int j = (i == len ? 1 : 0); j < n[i]; j++)	if (i == len || abs(j-n[i+1]) >= 2)	ret += f[i][j];
        if (i < len && abs(n[i+1]-n[i]) < 2)	break;
    }
    return ret;
}
int main() {
    for (int i = 0; i <= 9; i++)	f[1][i] = 1;
    for (int i = 1; i <= 10; i++)	for (int j = 0; j <= 9; j++) {
        for (int k = 0; k <= j-2; k++)	f[i+1][k] += f[i][j];
        for (int k = j+2; k <= 9; k++)	f[i+1][k] += f[i][j];
    }
    int l, r;	scanf("%d%d", &l, &r);	printf("%d", calc(r+1)-calc(l));
    return 0;
}