数位DP BZOJ 1026 [SCOI2009]windy数

题目链接

前面全是0的情况特判

#include <bits/stdc++.h>

int dp[10][10];
int digit[10];

int DFS(int pos, int val, int zero, bool limit) {
    if (pos == -1) {
        return 1;
    }
    int &now = dp[pos][val];
    if (!limit && zero && now != -1) {
        return now;
    }
    int d = limit ? digit[pos] : 9;
    int ret = 0;
    if (zero == 0) {
        for (int i=0; i<=d; ++i) {
            ret += DFS (pos - 1, i, i, limit && i == d);
        }
    } else {
        for (int i=0; i<=d; ++i) {
            if ((i-val) * (i - val) < 4) {
                continue;
            }
            ret += DFS (pos - 1, i, 1, limit && i == d);
        }
    }
    if (!limit && zero) {
        now = ret;
    }
    return ret;
}

int solve(int x) {
    int n = 0;
    while (x) {
        digit[n++] = x % 10;
        x /= 10;
    }
    int ret = 0;
    return DFS (n - 1, 0, 0, true);
}

int main() {
    memset (dp, -1, sizeof (dp));
    int a, b;
    while (scanf ("%d%d", &a, &b) == 2) {
        printf ("%d\n", solve (b) - solve (a - 1));
    }
    return 0;
}

  

时间: 05-15

数位DP BZOJ 1026 [SCOI2009]windy数的相关文章

bzoj 1026 [SCOI2009]windy数(数位DP)

1026: [SCOI2009]windy数 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 4550  Solved: 2039[Submit][Status][Discuss] Description windy定义了一种windy数.不含前导零且相邻两个数字之差至少为2的正整数被称为windy数. windy想知道,在A和B之间,包括A和B,总共有多少个windy数? Input 包含两个整数,A B. Output 一个整数. Sample

bzoj 1026 [SCOI2009]windy数 数位dp

1026: [SCOI2009]windy数 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/problem.php?id=1026 Description windy定义了一种windy数.不含前导零且相邻两个数字之差至少为2的正整数被称为windy数. windy想知道,在A和B之间,包括A和B,总共有多少个windy数? Input 包含两个整数,A B. Output 一个整数.

【数位DP】bzoj1026: [SCOI2009]windy数

1026: [SCOI2009]windy数 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 4163  Solved: 1864[Submit][Status][Discuss] Description windy定义了一种windy数.不含前导零且相邻两个数字之差至少为2的正整数被称为windy数. windy想知道,在A和B之间,包括A和B,总共有多少个windy数? Input 包含两个整数,A B. Output 一个整数. Sample

bzoj 1026 [ SCOI2009 ] windy数 —— 数位DP

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1026 蛮简单的数位DP,预处理 f[i][j] 表示 i 位数,以 j 开头的 windy 数个数: 但不明白为什么最后一位拿出来特判 ret++  不对,而写在循环里,特判 i==1 就对了... 代码如下: #include<iostream> #include<cstdio> #include<cstring> #include<algorithm&g

BZOJ 1026: [SCOI2009]windy数 【数位dp】

Description windy定义了一种windy数.不含前导零且相邻两个数字之差至少为2的正整数被称为windy数. windy想知道,在A和B之间,包括A和B,总共有多少个windy数? Input 包含两个整数,A B. Output 一个整数. Sample Input [输入样例一] 1 10 [输入样例二] 25 50 Sample Output [输出样例一] 9 [输出样例二] 20 HINT [数据规模和约定] 100%的数据,满足 1 <= A <= B <= 2

bzoj 1026 [SCOI2009]windy数——数位dp水题

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1026 迷恋上用dfs写数位dp了. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=15; int l,r,dg[N],dp[N][N]; int dfs(int p,int lst,bo

bzoj 1026 SCOI2009 windy数

Description windy定义了一种windy数.不含前导零且相邻两个数字之差至少为2的正整数被称为windy数. windy想知道, 在A和B之间,包括A和B,总共有多少个windy数? Input 包含两个整数,A B. Output 一个整数 Sample Input [输入样例一] 1 10 [输入样例二] 25 50 Sample Output [输出样例一] 9 [输出样例二] 20 HINT [数据规模和约定] 100%的数据,满足 1 <= A <= B <= 2

1026: [SCOI2009]windy数(数位dp)

1026: [SCOI2009]windy数 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 9016  Solved: 4085[Submit][Status][Discuss] Description windy定义了一种windy数.不含前导零且相邻两个数字之差至少为2的正整数被称为windy数. windy想知道,在A和B之间,包括A和B,总共有多少个windy数? Input 包含两个整数,A B. Output 一个整数 Sample I

【BZOJ】1026: [SCOI2009]windy数(数位dp)

http://www.lydsy.com/JudgeOnline/problem.php?id=1026 我果然很弱啊... 考虑数位dp.枚举每一位,然后限制下一位即可. 一定要注意啊!在dfs的时候line这个要&&啊....要不然wa了两发.. #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream>