数位DP -

算法概述

什么是数位DP：

数位DP往往都是这样的题型,给定一个闭区间[L,R]让你求这个区间中满足某种条件的数的总数。所谓数位dp,就是对数位进行dp,也就是个位、十位等

时间复杂度：O（logN）        

常用流程：

例题1：windy数

link:P2657 [SCOI2009] windy 数 - 洛谷

推荐题解（特别详细，强烈推荐）：题解 P2657 【[SCOI2009]windy数】 - 洛谷专栏

code

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll dp[15][10];//dp[i][j]:长度为i的最高位为j的所有数字对应的windy数数目
// 当j==0: dp[i][0] == dp[i-1][2] + dp[i-1][3] + ... + dp[i-1][9];ll work(ll n)// return [0, n)中的windy数，注意不包括n
{int a[15] = { 0 };int len = 0;while (n){a[++len] = n % 10;n /= 10;}ll ans = 0;// 若 n = 54321// 计算windy(0~9999), 不能直接ans+=dp[len][0],因为题目要求不算前导0，dp[len][0]中不包含dp[len - 1][1]与dp[len-1][0]for (int i = 1; i <= len - 1; i++)for (int j = 1; j <= 9; j++)ans += dp[i][j];// windy(10000~49999)for (int i = 1; i <= a[len] - 1; i++) ans += dp[len][i];// windy(50000~54321)for (int i = len - 1; i >= 1; i--){for (int j = 0; j < a[i]; j++)// 因不包含最后a[i],work(n)求的是windy([0, n)),左闭右开，即不包括n{if (abs(j - a[i + 1]) >= 2) ans += dp[i][j];}if (abs(a[i] - a[i + 1]) < 2) break;}return ans;
}void init()
{for (int i = 0; i <= 9; i++)dp[1][i] = 1;for (int len = 2; len <= 11; len++){for (int i = 0; i <= 9; i++){for (int k = 0; k <= 9; k++){if(abs(i-k) >= 2) dp[len][i] += dp[len - 1][k];}}}
}int main()
{ll a, b; cin >> a >> b;init();ll ans = work(b + 1) - work(a);// 只考虑上界cout << ans << endl;return 0;
}

例2：7的意志

link:7的意志

code

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int dig[20];
ll dp[20][10][10];// dp[len][sum%7][sum1%7]:所有的长度为len的...ll dfs(int pos, int sum, int sum1, int limit)// return 前pos数对应的7的意志数，如n=54321, pos = 2,则dfs return[0, 54]中7的意志数
{if (pos == 0) return sum1 == 0 && sum == 0;if (!limit && dp[pos][sum][sum1] != -1) return dp[pos][sum][sum1];// limit为false才可使用通用dpll res = 0;ll up = limit ? dig[pos] : 9;for (int i = 0; i <= up; i++){res += dfs(pos - 1, (sum * 10 + i) % 7, (sum1 + i) % 7, limit && (i == dig[pos]));}if(!limit)dp[pos][sum][sum1] = res;// (!limit意味着up为9，此时的dp[pos]具有通用性return res;
}ll work(ll n)// 计算[0, n]7的意志的个数
{ll len = 0;while (n){dig[++len] = n % 10;n /= 10;}memset(dp, -1, sizeof dp);return dfs(len, 0, 0, 1);
}int main()
{ll n, m; while (true){cin >> n >> m; if (n == 0 && m == 0)return 0;ll ans = work(m) - work(n - 1);cout << ans << endl;}
}