首页 > 代码库 > 【数位DP】

【数位DP】

2024-11-05 20:44:02   203人阅读

【总览】

通过将数拆分成一位位的进行dp（记忆化搜索），状态最基本的有：位置（$pos$），最高位限制（$limit$），前导零（$lead$），前一位（$pre$）等等，通常需要的状态视题目而定。

记忆化搜索的数组$dp$由多维构成，每一位都是一种状态的因素。

【bzoj】不要62

数位$dp$入门题，$dp$数组为$dp[pos][pre][limit]$（$limit$可以通过更改代码去掉这一维）。

【code】

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cstdlib>#include<cmath>using namespace std;const int N = 10;int as[N], bs[N], lena, lenb;long long dp[N][N][2];int a, b;inline int read(){    int i = 0, f = 1; char ch = getchar();    for(; (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘; ch = getchar());    if(ch == ‘-‘) f = -1, ch = getchar();    for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar())        i = (i << 3) + (i << 1) + (ch - ‘0‘);    return i * f;}inline void wr(long long x){    if(x < 0)putchar(‘-‘), x = -x;    if(x > 9) wr(x / 10);    putchar(x%10 + ‘0‘);}inline long long dfs(int pos, int last, bool limit, int *s, int l){    if(pos == l + 1) return 1;    if(dp[pos][last][limit] != -1) return dp[pos][last][limit];    int high = limit ? s[pos] : 9;    long long ret = 0;    for(int i = 0; i <= high; i++){        if(last == 6 && i == 2) continue;        if(i == 4) continue;        ret += dfs(pos + 1, i, limit && (i == high), s, l);    }    dp[pos][last][limit] = ret;    return ret;}int main(){    while(1){        a = read(), b = read();        if(!a && !b) break;        //----------------------------------        memset(dp, -1, sizeof dp);        memset(as, 0, sizeof as);        lena = 0;        if(a > b) swap(a, b);        int tmp;        tmp = a - 1;        while(tmp){            as[++lena] = tmp % 10;            tmp /= 10;        }        reverse(as + 1, as + lena + 1);        long long r1 = dfs(1, 0, 1, as, lena);        //----------------------------------                memset(dp, -1, sizeof dp);        memset(bs, 0, sizeof bs);        lenb = 0;        tmp = b;        while(tmp){            bs[++lenb] = tmp % 10;            tmp /= 10;        }        reverse(bs + 1, bs + lenb + 1);        long long r2 = dfs(1, 0, 1, bs, lenb);        //-------------------------------------        wr(r2 - r1), putchar(‘\n‘);    }}
View Code

 【bzoj】windy数

同样是入门级别的题，$dp$中加入前导零这一维（亦可更改代码去掉），当当前位可作为前导零时，有两种选择：

  • 继续前导零
  • 填上大于$0$的数，以后的数不能再使用“前导”$0$（普通$0$可以用）

若不能在作为前导$0$，则必须满足差值大于等于$2$的要求。

【code】

技术分享
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>#include<vector>using namespace std;const int N = 15;int dp[N][N][2][2]; //位置，前一个数，最高位限制int as[N], bs[N], lena, lenb, a, b;inline int dfs(int pos, int last, bool limit, bool lead, int *s, int l){    if(pos == l + 1) return 1;    if(dp[pos][last][limit][lead] != -1) return dp[pos][last][limit][lead];    int high = limit ? s[pos] : 9, ret = 0;    for(int i = 0; i <= high; i++){        if(!lead){            if(i != 0)ret += dfs(pos + 1, i, limit && i == high, 1, s, l);            else ret += dfs(pos + 1, i, limit && i == high, 0, s, l);        }        else if(abs(i - last) >= 2)            ret += dfs(pos + 1, i, limit && i == high, 1, s, l);    }    dp[pos][last][limit][lead] = ret;     return ret;}    int main(){    scanf("%d%d", &a, &b);    if(a > b) swap(a, b);    //------------------------    memset(dp, -1, sizeof dp);    int tmp = a - 1;    while(tmp) as[++lena] = tmp % 10, tmp /= 10;    reverse(as + 1, as + lena + 1);    int r1 = dfs(1, 0, 1, 0, as, lena);        memset(dp, -1, sizeof dp);    tmp = b;    while(tmp) bs[++lenb] = tmp % 10, tmp /= 10;    reverse(bs + 1, bs + lenb + 1);    int r2 = dfs(1, 0, 1, 0, bs, lenb);    cout<<r2 - r1<<endl;    return 0;}
View Code

 【cf】Beautiful Numbers

　学到了。本题难点在于离散压空间。若正常的进行$dp$，那么数组大小早就爆了。

  现在考虑这样一个问题：对于$1~9$的数而言，最小公倍数为2520. 由题知，设最后的数为$x$

　　数学推到知$a \equiv b (mod p) \Leftrightarrow q | a - b$

　　

【数位DP】


联系
我们