数位DP I（DFS式 + 递推式）
前言
明天要开学了 QAQQQQQ
数位DP是一种是一种计数技巧，目前蒟蒻看到的有递推式和DFS式两种
个人觉得，相对于递推式，DFS式要更易理解，因为DFS式实质上是普通的DFS加上记忆化数组（所以和DP有什么关系 = =||），而递推式则是能把DP方程列出来就ok
本篇大部分采用的是递推式，以后再发这一专题就要转DFS式了
- 数位DP
https://agatelee.cn/2016/04/%E6%95%B0%E4%BD%8Ddp/
https://wenku.baidu.com/view/9de41d51168884868662d623.html
https://www.dreamwings.cn/hdu2089/4950.html
https://blog.csdn.net/dslovemz/article/details/8540340
不要62 - HDU - 2089
思路 —— 数位DP（递推式）
和Zetsfy大佬聊这道题的时候，大佬认为暴力可解，结果暴力真的可解 = =||
说回数位DP，定义DP状态为dp[i][j]，代表当前为i位数，且最高位是j，那么dp[i][j] += dp[i - 1][k]; (j != 4 && (j, k) != (6, 2))
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 11;
ll dp[N][10];
void init(){
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i < N; i++){
for(int j = 0; j <= 9; j++){
if(j == 4) continue;
for(int k = 0; k <= 9; k++){
if(j == 6 && k == 2) continue;
dp[i][j] += dp[i - 1][k];
}
}
}
}
ll solve(int x){
int num[N] = {0}, tot = 0;
while(x){
num[++tot] = x%10;
x /= 10;
}
ll ans = 0;
for(int i = tot; i >= 1; i--){
for(int j = 0; j < num[i]; j++){ //到本身时后面已经不能跑到9，故不能 <=
if(num[i + 1] == 6 && j == 2) continue;
ans += dp[i][j];
}
if(num[i] == 4 || (num[i] == 2 && num[i + 1] == 6)) break;
}
return ans;
}
int main(){
init();
int l, r;
while(scanf("%d%d", &l, &r) && (l | r)){
printf("%lld\n", solve(r + 1) - solve(l));
}
}
思路 —— 数位DP（DFS式）
怎么搜索就怎么写，最后考虑哪些地方可以记忆化，加进去就完事了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 15;
ll dp[N][2], num[N];
int dfs(int i, bool lim, bool ispre_six){
if(i == 0) return 1;
if(lim == false && dp[i][ispre_six] != -1) return dp[i][ispre_six];
int up = lim ? num[i] : 9;
int ans = 0;
for(int j = 0; j <= up; j++){
if(j == 4 || (ispre_six && j == 2)) continue;
ans += dfs(i - 1, j == up && lim, j == 6);
}
if(lim == false) dp[i][ispre_six] = ans;
return ans;
}
int solve(int x){
memset(dp, -1, sizeof(dp));
int tot = 0;
while(x){
num[++tot] = x%10;
x /= 10;
}
return dfs(tot, true, false);
}
int main(){
int l, r;
while(~scanf("%d%d", &l, &r) && (l | r)){
printf("%d\n", solve(r) - solve(l - 1));
}
}
B-number - HDU - 3652
题意
求[1,n]数字中能被13整除且子串含有子串13的数量
思路
定义DP状态dp[i][j][k][p]，代表当前位数为i，首位为j，对13求余为k，且 包含13子串(k==1)/不包含13子串(k==0) 的数的数量，那么
dp[i][j][1][(j*10^(i - 1) + k)%13] += dp[i - 1][j'][1][k]
dp[i][j][0][(j*10^(i - 1) + k)%13] += dp[i - 1][j'][0][k] ,(j,j') != (1,3)
dp[i][1][1][(j*10^(i - 1) + k)%13] += dp[i - 1][3][0][k] ,(j,j') == (1,3)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 11;
ll dp[N][N][2][14]; //0: don't contain 13, 1: contain 13
void init(){
memset(dp, 0, sizeof(dp));
for(int j = 0; j <= 9; j++){
dp[1][j][0][j] = 1;
}
ll sum = 10;
for(int i = 2; i < N; i++){
for(int j = 0; j <= 9; j++){
for(int prek = 0; prek <= 12; prek++){
for(int prej = 0; prej <= 9; prej++){
if(j != 1 || prej != 3){
dp[i][j][0][(sum*j + prek)%13] += dp[i - 1][prej][0][prek];
}else{
dp[i][1][1][(sum*j + prek)%13] += dp[i - 1][3][0][prek];
}
dp[i][j][1][(sum*j + prek)%13] += dp[i - 1][prej][1][prek];
}
}
}
sum = sum * 10;
}
}
ll solve(int x){
int num[N] = {0}, tot = 0;
while(x){
num[++tot] = x%10;
x /= 10;
}
ll sum = 1;
for(int i = 1; i <= tot - 1; i++) sum = sum * 10;
ll ans = 0;
bool flag = false;
int k = 0;
for(int i = tot; i >= 1; i--){
for(int j = 0; j < num[i]; j++){
ans += dp[i][j][1][(-k + 13)%13];
if(flag || (num[i + 1] == 1 && j == 3)) ans += dp[i][j][0][(-k + 13)%13];
}
if(num[i] == 3 && num[i + 1] == 1){
flag = true;
}
k = (k + sum*num[i])%13;
sum /= 10;
}
return ans;
}
int main(){
init();
int n;
while(~scanf("%d", &n)){
printf("%lld\n", solve(n + 1));
}
}
Round Numbers - POJ - 3252
题意
求区间[l,r]中的数字写成二进制形式后0的数量大于等于1的数量的数字的个数
思路
本题的前导0对最终结果有影响，具体体现在前导0会增加0的个数
定义DP方程为dp[i][j][p][q][k]，代表当前为i位数，首位为j，0的数量有p个，1的数量有q个，且若这一位为0是否将其作为前导0（k==1则作为，否则不作为）的数字的数量，则
dp[i][0][p + 1][q][0] += dp[i - 1][0][p][q][0] + dp[i - 1][1][p][q][0]
dp[i][1][p][q + 1][0] += dp[i - 1][0][p][q][0] + dp[i - 1][1][p][q][0]
dp[i][0][p][q][1] += dp[i - 1][0][p][q][1] + dp[i - 1][1][p][q][0]
值得注意的是第三条，对作为前导0的部分，不计前导0中的0的数量
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 33;
ll dp[N][2][N][N][2];
void init(){
memset(dp, 0, sizeof(dp));
dp[1][0][1][0][0] = dp[1][1][0][1][0] = 1, dp[1][0][0][0][1] = 1;
for(int i = 2; i < N; i++){
for(int p = 0; p < N; p++){
for(int q = 0; q < N; q++){
dp[i][0][p + 1][q][0] += dp[i - 1][0][p][q][0] + dp[i - 1][1][p][q][0];
dp[i][1][p][q + 1][0] += dp[i - 1][0][p][q][0] + dp[i - 1][1][p][q][0];
dp[i][0][p][q][1] += dp[i - 1][0][p][q][1] + dp[i - 1][1][p][q][0];
}
}
}
}
ll solve(int x){
int num[N] = {0}, tot = 0;
while(x){
num[++tot] = x%2;
x /= 2;
}
ll ans = 0;
int cur = 0; //记录0的数量比1的数量多多少
for(int i = tot; i >= 1; i--){
for(int j = 0; j < num[i]; j++){
for(int p = 0; p < N; p++){
for(int q = 0; q <= p + cur && q < N; q++){
//当i位于首位且这一位dp到0时，需要使用作为前导0的dp结果
if(i == tot && j == 0) ans += dp[i][j][p][q][1];
else ans += dp[i][j][p][q][0];
}
}
}
if(num[i] == 0) cur++;
else cur--;
}
return ans;
}
int main(){
init();
int l, r;
while(~scanf("%d%d", &l, &r)){
printf("%lld\n", solve(r + 1) - solve(l));
}
}
