HYSBZ 1026： windy数（数位DP）

类型：数位DP
题意：不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。问[A,B]之间windy数的个数。(1 <= A <= B <= 2000000000 )

思路：

设状态dp[i][d][preAllZero] 表示 d开头的i位数中，当其preAllZero（true 表示前面都是0）的时候，windy数的个数。

为什么有preAllZero这一个状态呢？因为，比如002这个数，如果前面都是0,则是可以的，但如果前面有一位不是0 ，则这两个0违反了windy数的规则，就不行。

转移就不写了。见程序就好。

坑：

没有设preAllZero这个状态，结果一直WA。最近发现老是考虑不完全，结合近两次的原因分析，均为有了思路写程序，写完或者写到一半发现某个地方想错了，然后打补丁，结果没打全，就出了漏洞。总结两点：1：先有清晰的思路，再上阵写程序，只会节省时间。（在纸上思考要时间，你以为敲代码的时候这部分时间就省了？反而是在纸上想完全，然后敲代码的时候就可以不用想了，快啊~~）2：万一敲完发现BUG，打完补丁还不对，最好推倒，重新整理思路，然后再去写（但也不是说要把程序删了重写，或许并没到这个地步，只是没想全而已~）

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int num[];

long long dp[][][];

long long dfs(int i, int d, bool preAllZero, bool isQuery) {

    if (!isQuery && ~dp[i][d][preAllZero]) return dp[i][d][preAllZero];

    if (i == ) {

        return dp[i][d][preAllZero] = ;

    }

    int end = isQuery?num[i-]:;

    long long ans = ;

    for (int j = ; j <= end; j++) {

        if (!preAllZero && abs(j-d)<=) continue;

        ans += dfs(i-, j, preAllZero && j == , isQuery && j==end);

    }

    if (!isQuery) dp[i][d][preAllZero] = ans;

    return ans;

}

long long cal(int x) {

    int len = ;

    while (x) {

        num[++len] = x%;

        x/=;

    }

    return dfs(len+, , true, true);

}

int main() {

    int a, b;

    memset(dp, -, sizeof(dp));

    while (~scanf("%d%d", &a, &b)) {

        printf("%lld\n", cal(b) - cal(a-));

    }

    return ;

}

巴特西

HYSBZ 1026： windy数（数位DP）

最新文章

热门文章