数位DP板子

数位dp，好题总结：
一道统计[l, r]内回文数字数量的题目：
Palindromic Numbers

• 简单来说就是在一串数字的前一半放各种数字，后一半不仅要放，还得与前面对称位置的数匹配，才能把所需的状态传下去
• 开一个数组保存非常巧妙

  注意这里数位dp的pos是从大到小的，pos最大表示的是数的最高位。所以只有当pos小于总长度的一半时，才是来到了数的"后半段”，才需要与前半段的对应位置比较是否相等，然后传递匹配状态信息。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 32;
int nums[N], a[N]; 
LL f[N][N][2]; 
LL l, r;
int k, len;

//pos:当前走到的位置，s:回文串的起始位置，flag:当前串是否是回文串
//lead: 是否有前导0，limit: 当前位是否有最大限制
LL dfs(int pos, int s, bool flag, bool lead, bool limit){
	if(!pos) return flag;
	if(!lead && !limit && ~f[pos][s][flag]) return f[pos][s][flag];
	LL ans = 0, up = limit ? nums[pos] : 9;
	for(int i = 0; i <= up; i++){
		a[pos] = i;
		if(lead && i == 0){
			ans += dfs(pos - 1, s - 1, flag, lead, limit && i == up);
		}
		else{
			if(flag && pos <= s / 2){
				ans += dfs(pos - 1, s, i == a[s + 1 - pos], lead && i == 0, limit && i == up);
			}
			else{
				ans += dfs(pos - 1, s, flag, lead && i == 0, limit && i == up);
			}
		}
	}
	if(!lead && !limit) f[pos][s][flag] = ans;
	return ans;
}

LL calc(LL x){
	memset(f, -1, sizeof f);
	len = 0;
	while(x){
		nums[++len] = x % 10;
		x /= 10;
	}
	return dfs(len, len, 1, 1, 1);
}

void solve(){
	scanf("%lld%lld", &l, &r);
	if(l > r) swap(l, r);
	printf("Case %d: %lld\n", ++k, calc(r) - calc(l - 1));

}

int main(){
	int _ = 1; scanf("%d", &_);
	while(_ -- ) solve();
	return 0;
}

——该板子来自凌乱之风，风神的总结~，ORZ

  初始时，$lead = 1, limit = 1$。当成有前导零；有限制，否则第一位就能随便填了。

  $pos$ 的减对应的是数字从高位到低位的顺序。

  $dp$ 数组是对 $pos$ 和一些重要参数的记忆化。有前导 $0$ 是一种特殊情况，说明枚举到这一位前面都是 $0$，所以该情况是唯一的；有限制也是一种特殊情况，说明当前位的取法对应的数也是唯一的。因此只有当 !lead && !limit时，才需要进行记忆化。