数位 dp，但是做题笔记

这玩意儿还要学自己推不出来的 SX 是屑。

数位 dp，顾名思义，是根据数位做 dp，每个数位每个数位转移，炒个例子 windy 数。

求 \([l, r]\)，我们改成求 \(1\sim r\) 与 \(1\sim (l - 1)\) 最后二者相减。那么我们的问题就成了求 \(1\sim k\) 的 windy 数。运用 dp，数位 dp 每次从最高位往最低位填数，首先我们要知道填到第几位 \(i\)。由于是填数，但是填的数字不能超过限定范围，因此我们加一维记录前 \(i - 1\) 位是否与 \(k\) 的前 \(i - 1\) 位相同，如果相同则 \(i\) 位最多只能填到 \(k\) 的第 \(i\) 位否则能填到 \(9\)，同时我们还要记录 \(i\) 是不是前导 0。

通常的数位 dp 的状态是个三元组，\(f_{i, 0/1, 0/1}\) 代表填到了 \(i\) 位与 \(k\) 的前 \(i - 1\) 位是否一致，\(i\) 是否是前导 \(0\)。这是个板子（笑）。这题我们还要加入一个 \(last\) 代表 \(i\) 的下一位填的是什么。因此我们的状态是 \(f_{i, last, 0/1, 0/1}\)。

转移应该很显然。。。用记搜，因为用迭代写起来很难受。

//SIXIANG

#include <iostream>

#include <cstring>

#define int long long

#define MAXN 100000

#define QWQ cout << "QWQ" << endl;

using namespace std;

int arr[MAXN + 10], t = 0;

void divide(int x) {

	do {

		arr[++t] = x % 10;

		x /= 10;

	} while(x);

}

int f[100][15][2][2];

int Abs(int x) {

	if(x < 0) return -x;

	else return x;

}

//填到第 i 位上个数是 last 前 (i - 1) 位是否与 k 相同

int windy(int i, int last, int fa, int ze) {

	if(!i) return 1;

	if(f[i][last][fa][ze] != -1) return f[i][last][fa][ze];

	int limit = ((fa) ? arr[i] : 9);

	int rest = 0;

	for(int p = 0; p <= limit; p++)

		if(Abs(p - last) >= 2 || ze)

			rest += windy(i - 1, p, ((p == arr[i]) & fa), (ze & (!p)));

	f[i][last][fa][ze] = rest;

	return rest;

}

int work(int k) {

	memset(f, -1, sizeof(f));

	memset(arr, 0, sizeof(arr));

	t = 0;

	divide(k);

	return windy(t, 11, 1, 1);

}

signed main() {

	int l, r; cin >> l >> r;

	cout << work(r) - work(l - 1) << endl;

}

巴特西

数位 dp，但是做题笔记

最新文章

热门文章