洛谷p1831 数位dp

补充点在其他题解里面没有的其他东西。

首先是之所以可以数位dp并且不会算错的原因是，对于每一个数字，如果这个数字是杠杆数，那么他的支点有且只有一个，如果一个数字有多个支点，那么数位dp去枚举支点就会算重复，算多。

另外全部人都是在说数位dp然后枚举支点，对R和L-1分别做一次dp，但是可以有个小优化就是，我们要明确一个东西，dp数组存的是那些没有被限制的的有用数字是数量，也就是对于任意数都适用。

那么我们可以发现在枚举支点位置的时候，枚举位置1，对于R和L-1都分别去dfs了一次，但是实际上所做的效果是一样的，因为对于没有被限制的数字他的数量是不会变的，所以我们可以把两个数字一起来算，每一次枚举支点都可以一次性统计。

int solve(int x,int y) {//L, R
	memset(dp, -127, sizeof(dp));
	int pos1 = 0,pos2 = 0;
	while (x) {
		num[1][pos1++] = x % 10;
		x /= 10;
	}
	while (y) {
		num[2][pos2++] = y % 10;
		y /= 10;
	}
	int ans1 = 0,ans2 = 0;
	for (int i = 0; i < 17; i++) {
		ans2 += dfs(pos2 - 1, true, 0, i, 0, 2);
		ans1 += dfs(pos1 - 1, true, 0, i, 0, 1);
	}
	return ans2 - ans1;
}

这是我是solve函数，枚举所有的支点位置，然后一起统计就可以了，这样就可以充分的利用之前跑出一遍所获得的贡献，在一个另外的点就是，你还可以在开一个维度，那个维度代表的就是你现在枚举的是哪个支点，就是空间换时间，你就可以不用每次枚举支点的时候都来一次memset。