首页 > 代码库 > [BZOJ 1026] [SCOI 2009] Windy数 【数位DP】
[BZOJ 1026] [SCOI 2009] Windy数 【数位DP】
题目链接:BZOJ - 1026
题目分析
这道题是一道数位DP的基础题,对于完全不会数位DP的我来说也是难题..
对于询问 [a,b] 的区间的答案,我们对询问进行差分,求 [0,b] - [0,a-1] 的答案。这样就化繁为简了。
具体过程见代码中的注释。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxBit = 13;int A, B;int f[MaxBit][11], Bit[MaxBit];inline int Abs(int a) { return a >= 0 ? a : -a;}//计算小于x的数的答案 int Get(int x) { if (x == 0) return 0; int ret = 0, l = 0; while (x) { Bit[++l] = x % 10; x /= 10; } //统计位数不足l位的答案 for (int i = 1; i <= l - 1; ++i) { for (int j = 1; j <= 9; ++j) { ret += f[i][j]; } } //固定后面的(l-i)位,然后第i位可以在[0, Bit[i]-1]之间变化 for (int i = 1; i <= Bit[l] - 1; ++i) ret += f[l][i]; for (int i = l - 1; i >= 1; --i) { for (int j = 0; j <= Bit[i] - 1; ++j) { if (Abs(j - Bit[i + 1]) >= 2) ret += f[i][j]; } //无法固定第i位 if (Abs(Bit[i + 1] - Bit[i]) < 2) break; } return ret;}int main() { //f[i][j]表示第i位是j的答案数 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 <= 9; ++k) { if (Abs(k - j) >= 2) f[i][j] += f[i - 1][k]; } } } scanf("%d%d", &A, &B); //对询问进行差分,化繁为简 printf("%d\n", Get(B + 1) - Get(A)); return 0;}
[BZOJ 1026] [SCOI 2009] Windy数 【数位DP】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。