动态规划扩展版数位dp模板题
做法与上一题 AcWing 1083. Windy数 类似
计算一个区间内所有满足要求的数
状态表示
f[i][j][k]
表示最高有i位,且最高位为j,且各位数字之和mod p的值为k的所有方案的个数
状态计算
类似背包问题,根据最后一位i
的选择的数j
进行划分,因为j
是一定要选的,所以第i - 1
位的状态需要预留出j
的空间
最终的状态转移方程为: f[i][j][k] += f[i - 1][x][mod(k - j,p)];
假设前面位数的各位数字之和为last,那么它再加上多少可以使得 mod N 的结果为0?
答案是加上mod(-last,p) 结果加上f[i + 1][j][mod(-last,p)]即计算出了当前左分支满足要求的数
c++代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 11,M = 110;
int f[N][10][M];
//f[i][j][k]表示最高有i位,且最高位为j,且各位数字之和mod p的值为k
int x,y,p; //[x,y]范围内 p表示要取模的数
int mod(int x,int y){ //规律取模只能为正数
return (x % y + y) % y;
}
void init(){
memset(f,0,sizeof f);
//初始化,只有一位数
for(int i = 0; i <= 9;++i) f[1][i][i % p]++;
for(int i = 2;i < N;++i){ //枚举位数
for(int j = 0;j <= 9;++j){ //枚举最高位
for(int k = 0;k < p;++k){ //枚举余数
for(int x = 0;x <= 9;++x){ // 枚举第i - 1位可以填的数
f[i][j][k] += f[i - 1][x][mod(k - j,p)];
}
}
}
}
}
int dp(int n){
if(!n) return 1;
vector<int> nums;
while(n) nums.push_back(n % 10), n /= 10;
int res = 0;
int last = 0; //记录前面位数累计的结果
//从最高位开始枚举
for(int i = nums.size() - 1;i >= 0;--i){
int x = nums[i];
//左分支,计算最高位取0 ~ x - 1的所有满足的数,直接用dp求
for(int j = 0; j < x;++j){
//预处理好了,直接查表
/*例如last为21,且p为4的情况下,那么可以加的数就是从剩下位数中取,且各位数字之和等于3,7,.....这些数,
即f[i + 1][j][mod(-last,p)]表示这些数的个数,所以方案数res累加这个数即可
*/
res += f[i + 1][j][mod(-last,p)]; //(last + mod(last,p) ) % p结果等于0
}
//进入右分支
last += x;
//到了最后一位数了,并且前面所有数包含自己 % p 的结果为0,那么就是合法的
if(!n && last % p == 0) res++;
}
return res;
}
int main(){
while(cin >> x >> y >> p){
init();
cout << dp(y) - dp(x - 1) << endl;
}
return 0;
}
第一张图有问题吧?计算还剩2位数时,左侧和下降有什么关系?不应该是次高位为0~5吗?怎么是3~5
最后是 ! i 吧, 不是 ! n
第二张图那里,last应该是前面到a(n-2)的总和吧,last定义不是前面位数的总和吗?应该是不包括x。
各位数之和才包含x。 求解疑
我的理解是是这样的,看状态转移,图上写的x是上个循环nums的第i位数,状态转移完才加到last里,计算当前状态时last用的是上一个循环的last值,所以这个x是包含在last里面的
嗯,我理解你的意思了,着眼点不同,你是以上次循环之后得到的last为准则,我是以当前x作为准则