「SCOI2009」windy数

题目链接:洛谷2657

Description

求在$[l,r]$中有多少个数满足每两个相邻数位的差值$\geq 2$。

Data Range

$1\leq l\leq r\leq 2000000000$

Solution

考虑数位DP。
$f[i][j]$表示当前考虑第$i$个数位,前一个数位的数字为$j$的方案数。
方程应该非常好得出吧。

Code

#include <bits/stdc++.h>

using namespace std;

long long f[15][11];
int dig[15], dct;

long long dfs(int pos, bool lead, bool limup, int last_num) {
  if (!pos) {
    return 1;
  }
  if (!lead && !limup && last_num != -1 && f[pos][last_num] != -1) {
    return f[pos][last_num];
  }
  int up = limup ? dig[pos] : 9;
  long long res = 0; 
  for (int i = 0; i <= up; i++) {
    if (lead) {
      if (!i) {
        res += dfs(pos - 1, 1, limup && (i == up), -1);
      } else {
        res += dfs(pos - 1, 0, limup && (i == up), i);
      }
    } else {
      if (abs(i - last_num) < 2) continue; 
      res += dfs(pos - 1, 0, limup && (i == up), i); 
    }
  }
  if (!lead && !limup && last_num != -1) {
    f[pos][last_num] = res;
  }
  return res;
}

long long solve(long long x) {
  for (dct = 0; x; x /= 10) {
    dct++;
    dig[dct] = x % 10;
  }
  return dfs(dct, 1, 1, -1); 
}

int main() {
  memset(f, -1, sizeof f);
  long long l, r;
  cin >> l >> r;
  cout << solve(r) - solve(l - 1) << '\n';
  return 0; 
}
最后修改:2019 年 09 月 07 日 08 : 08 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论