【数位DP】【P2657】[SCOI2009]windy数

Description

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为 \(2\) 的正整数被称为windy数。 windy想知道，

在 \(A\) 和 \(B\) 之间，包括 \(A\) 和 \(B\)，总共有多少个windy数？

Limitation

\(1 \leq A \leq B \leq 2000000000\)

Solution

前天重写这个题，换了一种比较好写的DP方式，这里记下来。

考虑由于前导 \(0\) 和顶上界都最多可能有 \(1\) 中方案，因此直接使用一个 bool 变量记录即可。

设 \(f_{i, j}\) 是考虑前 \(i\) 位，第 \(i\) 位是 \(j\) 且不顶上界的方案数，这样的转移就非常好写了。、

Code

#include <cmath>

#include <cstdio>

#include <cstring>

const int maxn = 100;

int x, y;

int A[maxn], B[maxn];

ll frog[maxn][10];

int ReadNum(int *p);

ll calc(const int *const num, const int n);

int main() {

  freopen("1.in", "r", stdin);

  int x = ReadNum(A); y = ReadNum(B);

  for (int i = x - 1; ~i; --i) {

    if ((--A[i]) >= 0) {

      break;

    } else {

      A[i] = 9;

    }

  }

  if (A[x] == 0) { --x; }

  qw(calc(B, y) - calc(A, x), '\n', true);

  return 0;

}

int ReadNum(int *p) {

  auto beg = p;

  do *p = IPT::GetChar() - '0'; while ((*p < 0) || (*p > 9));

  do *(++p) = IPT::GetChar() - '0'; while ((*p >= 0) && (*p <= 9));

  return p - beg;

}

ll calc(const int *const num, const int n) {

  if (n <= 1) {

    return num[0];

  }

  memset(frog, 0, sizeof frog);

  bool upc = true;

  for (int i = 1; i < num[0]; ++i) {

    frog[0][i] = 1;

  }

  for (int i = 1; i < n; ++i) {

    int di = i - 1;

    for (int j = 0; j < 10; ++j) {

      for (int k = 0; k < 10; ++k) if (abs(j - k) >= 2) {

        frog[i][j] += frog[di][k];

      }

      ++frog[i][j];

    }

    --frog[i][0];

    if (upc) {

      for (int k = 0; k < num[i]; ++k) if (abs(num[di] - k) >= 2) {

        ++frog[i][k];

      }

      if (abs(num[di] - num[i]) < 2) {

        upc = false;

      }

    }

  }

  ll _ret = 0;

  for (int i = 0, dn = n - 1; i < 10; ++i) {

    _ret += frog[dn][i];

  }

  return _ret + upc;

}

巴特西

【数位DP】【P2657】[SCOI2009]windy数

Description

Limitation

Solution

Code

最新文章

热门文章