https://blog.csdn.net/csyifanZhang/article/details/106572392

↑完整教程

#define inf 0x3f3f3f3f
#define MAX 1000005
#define ll long long
#define vec vector<ll>
#define P pair<int,int>

ll dp[15][10];//dp[i][j]:位数为i，最高位为j时最多有多少windy数

//统计[1,x)区间内的windy数
ll cal(ll x) {
	ll a[11], len = 0;
	while (x > 0) {
		a[++len] = x % 10;
		x /= 10;
	}
	ll sum = 0;
	//1:统计位数比x少的
	for (int i = 1; i < len; i++)
		for (int j = 1; j < 10; j++)//注意这里从1开始，最高位不能为0！
			sum += dp[i][j];
	//2:统计位数和x一样，但是首位比x小的，同样最高位不能为0
	for (int i = 1; i < a[len]; i++)
		sum += dp[len][i];
	//3:统计位数与x一样，首位也一样的，那么之前的每一位加上限制a[i]
	for (int i = len - 1; i >= 1; i--) {
		for (int j = 0; j < a[i]; j++)  //注意该位的限制，由于不是最高位，可以从0开始
			if (abs(j - a[i + 1]) >= 2)//该位和上一位满足要求
				sum += dp[i][j];
		if (abs(a[i + 1] - a[i]) < 2)//传入数字连续两位不满足了
			break;
	}
	return sum;
}

int main() {
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < 10; i++)dp[1...