动态规划扩展版数位dp模板题
本题与 AcWing 1082. 数字游戏 做法类似。
注意本题不允许前导零,那么就意味着,只能计算到位数为nums.size()
位的数,对于位数为0 ~ nums.size() - 1
的数来说就要另外加上
例如 判断数字357
因为指挥遍历不含前导零的数,所以最高位数只能为1,2,3,所以计算数只有100 ~ 357,
例如对于数字035,就不会计算到,所以对于位数为1和2的数要另外计算
如何算[0,y]之内的windy数
状态表示
f[i][j]
表示一共有i
位,且最高位为j
中所有数中满足windy数的个数
状态计算
当前位的数只要满足与前一位的差值为2即为合法,所以状态转移的方程是:
for(int i = 2;i <= N;++i){ //枚举位数
for(int j = 0;j <= 9;++j){ //枚举当前位的数
for(int k = 0;k <= 9;++k){ //枚举上一位的数
if(abs(j - k) >= 2) f[i][j] += f[i - 1][k];
}
}
}
C++代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int N = 15;
int f[N][10];
//f[i][j]表示一共有i位,且最高位为j中的所有数中满足windy数的个数
int x,y;
void init(){
//总共1位,最高位为i的个数为1(注意看题目样例,1 ~ 10里面有9个windy数)
for(int i = 0; i <= 9; i++) f[1][i] = 1;
for(int i = 2;i <= N;++i){ //枚举位数
for(int j = 0;j <= 9;++j){ //枚举当前位的数
for(int k = 0;k <= 9;++k){ //枚举上一位的数
if(abs(j - k) >= 2) f[i][j] += f[i - 1][k];
}
}
}
}
int dp(int n){
if(!n) return 0; //因为当n=0时,下面的while循环无法通过,所以要进行特判
vector<int> nums;
while(n) nums.push_back(n % 10) , n /= 10;
int res = 0;
//一开始初始成-1是为了第一位数字能取到1(不包含前导0,所以第一位不能取0)
int last = -1; //记录上一位的数(windy数也是只与前面相邻的数有关系)
//从高位往低位枚举
//因为前导零的情况都被判定不合法了,所以位数小于nums.size()的数就不会被计算不来(例:035)
//重点(这里只是计算了位数为nums.size()的数中满足要求的数,那么其他小于nums.size()还要单独拿出来计算)
for(int i = nums.size() - 1;i >= 0;--i){
int x = nums[i];
//左分支(枚举0 ~ nums[x] - 1 的数,以这些数为最高位可以直接dp来算)
//注意最高位不能取0(因为不包含前导零)
for(int j = (i == nums.size() - 1) ? 1 : 0;j < x;++j){
//只要与上一个数的差值大于2,就是合法的windy数
if(abs(j - last) >= 2)res += f[i + 1][j];
}
//不合法
if(abs(x - last) < 2) break;
last = x; // 走到右分支
//走到最后一位数了,并且没有被break出来,说明也是合法的
if(!i) res++;
}
//还要单独计算位数小于nums.size()的数(即特殊处理存在前导零的情况)
for(int i = 1;i <= nums.size() - 1;++i){
for(int j = 1;j <= 9;++j){
res += f[i][j];
}
}
return res;
}
int main(){
init();
cin >> x >> y;
cout << dp(y) - dp(x - 1) << endl;
return 0;
}