数位 dp
By WyyOIer |
2021-06-06 09:22:04 /
2022-08-27 17:26:52
nan

感觉数位DP用记忆化搜索挺简单的。

数位DP记忆化搜索模板

ll n, a[maxn];
ll dp[maxn][state]; //代表当前到了第 pos 位,某种状态 state 时的答案,state可以为多个状态。

ll dfs(int pos, int state, bool lead, bool limit) { //pos,state 同上,lead 代表是否有前导0,limit 代表是否可以取到原数。

    if(pos == 0) return 1; //所有数位搜索完成
    if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state]; //记忆化
    int up;
    if(!limit) up = 9; //这一位可以取 0~9
    else up = a[pos]; //否则不能超过要求数位
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        特殊判断;
        ans += dfs(pos-1, state, (lead == true && i == 0),(limit == true && i == a[pos]));//这里的 state 是更新后的 state。
    }
}

ll solve(ll x) {
    memset(dp, -1, sizeof(dp));
    int top = 0;
    while(x != 0) {
        a[++top] = x % 10;
        x /= 10;
    }
    return dfs(top, state, true, true);
}

题目

P2657 [SCOI2009]windy数

$dp[pos][state]$ 表示当前位为 $pos$,$pos+1$ 位选择 $state$,然后和当前位的选择判断即可。

const int maxn = 15;
ll a[maxn];
ll dp[maxn][10];

ll dfs(int pos, int state, bool lead, bool limit) {
    if(pos == 0) return 1;
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    int up;
    if(!limit) up = 9;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        if(abs(i - state) < 2) continue;	
        if(lead == true && i == 0) ans += dfs(pos-1, -2, true, (limit == true && i == a[pos]));
        else ans += dfs(pos-1, i, false, (limit == true && i == a[pos]));
    }
    if(!limit && !lead)
        dp[pos][state] = ans;
    return ans;
}

ll solve(ll x) {
    memset(dp, -1, sizeof(dp));
    int top = 0;
    while(x != 0) {
        a[++top] = x % 10;
        x /= 10;
    }
    return dfs(top, -2, true, true);
}

P4124 [CQOI2016]手机号码

$dp[pos][num1][num2][used4][used8][triple]$ 表示当前位为 $pos$,$pos+1$ 位为 $num1$,$pos+2$ 位为 $num2$,是否有$4$,是否有$8$,是否有三位连续的数。

const int maxn = 20;
ll a[maxn];
ll dp[maxn][10][10][2][2][2];

ll dfs(int pos, int num1, int num2, bool used4, bool used8, bool triple, bool lead, bool limit) {
    if(pos == 0) return triple;
    if(!limit && !lead && dp[pos][num1][num2][used4][used8][triple] != -1) return dp[pos][num1][num2][used4][used8][triple];
    int up;
    if(!limit) up = 9;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        if(used4 == true && i == 8) continue;
        if(used8 == true && i == 4) continue;
        if(lead == true && i == 0) ans += dfs(pos - 1, 0, -1, used4, used8, triple, true, (limit == true && i == a[pos]));
        else ans += dfs(pos-1, i, num1, (used4 == true || i == 4), (used8 == true || i == 8), (triple == true || (i == num1 && i == num2)), false, (limit == true && i == a[pos]));
    }
    if(!limit && !lead)  
        dp[pos][num1][num2][used4][used8][triple] = ans;
    return ans;
}

ll solve(ll x) {
    memset(dp, -1, sizeof(dp));
    int top = 0;
    while(x != 0) {
        a[++top] = x % 10;
        x /= 10;
    }
    return dfs(top, 0, -1, false, false, false, true, true);
}

P2602 [ZJOI2010]数字计数

本来我的状态为 $dp[pos]$ 表示当前位为 $pos$,含有查找数位的数量。

但是在记忆化时有一个问题

假设我要去找$1$的个数

例如$11110…$,$10234…$这两个数都已经搜了$5$位,则这两个数的状态都是一样的,但很明显前者$1$的数量要比后者的多,所以这个状态不对。

那么怎么才是对的呢?

发现 $11000…$,$12410…$这两个数当前$1$的个数一样,而最后总共$1$的个数应该也是一样的

那么状态定义 $dp[pos][cnt]$ 表示当前位 $pos$,含有 $cnt$ 个查找数位的数量。

const int maxn = 15;
ll a[maxn];
ll dp[maxn][maxn];

ll dfs(int pos, int key, ll cnt, bool lead, bool limit) {
    if(pos == 0) return cnt;
    if(!lead && !limit && dp[pos][cnt] != -1) return dp[pos][cnt];
    int up;
    if(!limit) up = 9;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        if(lead == true && i == 0) ans += dfs(pos-1, key, cnt, true, (limit == true && i == a[pos]));
        else ans += dfs(pos-1, key, cnt + (i == key), false, (limit == true && i == a[pos]));
    }
    if(!lead && !limit) 
        dp[pos][cnt] = ans;
    return ans;
}

ll solve(ll x,int key) {
    memset(dp, -1, sizeof(dp));
    int top = 0;
    while(x != 0) {
        a[++top] = x % 10;
        x /= 10;
    }
    return dfs(top, key, 0, true, true);
}

P3286 [SCOI2014]方伯伯的商场之旅

梁伯伯

借用老师的题解:


const int maxn = 50;
const int maxsum = 4000;
ll k, a[maxn];
ll dp[maxn][maxsum];

ll dfs1(int pos, ll sum, bool lead, bool limit) {
    if(pos == 0) return sum;
    if(!limit && !lead && dp[pos][sum]!=-1) return dp[pos][sum];
    int up;
    if(!limit) up = k - 1;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        if(lead == true && i == 0) ans += dfs1(pos-1, sum, true, (limit == true && i == a[pos]));
        else ans += dfs1(pos-1, sum + i * (pos - 1), false, (limit == true && i == a[pos]));
    }
    if(!limit && !lead)
        dp[pos][sum] = ans;
    return ans;
}

ll dfs2(int pos, ll state, bool lead, bool limit, int key) {
    if(state < 0) return 0;
    if(pos == 0) return state;
    if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
    int up;
    if(!limit) up = k - 1;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        if(lead == true && i == 0) ans += dfs2(pos-1, state, true, (limit == true && i == a[pos]), key);
        else if(pos >= key) ans += dfs2(pos - 1, state + i, false, (limit == true && i == a[pos]), key);
        else ans += dfs2(pos - 1, state - i, false, (limit == true && i == a[pos]), key);
    }
    if(!limit && !lead)
        dp[pos][state] = ans;
    return ans;
}

ll solve(ll x) {
    memset(dp, -1, sizeof(dp));
    int top = 0;
    while(x != 0) {
        a[++top] = x % k;
        x /= k;
    }
    ll ans = dfs1(top, 0, true, true);
    for(int i = 2;i <= top;i++) {
        memset(dp, -1, sizeof(dp));
        ans -= dfs2(top, 0, true, true, i);
    }
    return ans;
}

P4317 花神的数论题

双倍经验题。

状态同 P2602 [ZJOI2010]数字计数。

const int maxn = 50;
ll a[maxn];
ll dp[maxn][maxn];

ll dfs(int pos, ll cnt, bool lead, bool limit) {
    if(pos == 0) return max(cnt, 1);
    if(!limit && !lead && dp[pos][cnt] != -1) return dp[pos][cnt];
    int up;
    if(!limit) up = 1;
    else up = a[pos];
    ll ans = 1;
    for(int i = 0;i <= up;i++) {
        if(lead == true && i == 0) ans = (ans * dfs(pos - 1, cnt, true, (limit == true && i == a[pos]))) % Mod;
        else ans = (ans * dfs(pos - 1, cnt + i, false, (limit == true && i == a[pos]))) % Mod;
    }
    if(!limit && !lead)
        dp[pos][cnt] = ans;
    return ans;
}

ll solve(ll x) {
    memset(dp, -1, sizeof(dp));
    int top = 0;
    while(x != 0) {
        a[++top] = x % 2;
        x /= 2;
    }
    return dfs(top, 0, true, true);
}

P4999 烦人的数学作业

思路同 P2602 [ZJOI2010]数字计数。

设状态 $dp[pos][sum]$ 表示当前位为 $pos$,数字和为 $sum$ 的答案。

const int maxn = 20+5;
const int maxsum = 200+5;
ll a[maxn];
ll dp[maxn][maxsum];

ll dfs(int pos, int sum, bool lead, bool limit) {
    if(pos == 0) return sum;
    if(!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
    int up;
    if(!limit) up = 9;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++)
        ans = (ans + dfs(pos - 1, sum + i, (lead == true && i == 0), (limit == true && i == a[pos]))) % Mod;
    if(!limit && !lead)
        dp[pos][sum] = ans;
    return ans;
}

ll solve(ll x) {
    memset(dp, -1, sizeof(dp));
    int top = 0;
    while(x != 0) {
        a[++top] = x % 10;
        x /= 10;
    }
    return dfs(top, 0, true, true);
}

T180087 花式打牌

这题我想吐槽一下,比赛的时候一直在想容斥,结果喜提$0$分qwq

但如果将每种牌选出的数量当做一个数位,发现可以用数位 dp

考虑分 $\text{op}$ 去写。

$\text{op}=1$,状态 $dp[pos][rest][ok]$ 表示当前位为 $pos$,剩余 $rest$ 张,是否有炸弹。

$\text{op}=2$,状态 $dp[pos][rest][last][ok]$ 表示当前位为 $pos$,剩余 $rest$ 张,$pos+1$ 位为 $last$,是否有飞机。

$\text{op}=3$,发现用四维状态表示前四位的选择空间开销过大,但其实可以只用一维表示已经连续了几种牌。

$\text{op}=4$

若将状态定为 $dp[pos][rest][cnt][last][ok1][ok2][ok3]$ 表示当前位为 $pos$,剩余 $rest$ 张,已经连续了 $cnt$ 为,上一位为 $last$,是否有炸弹,是否有飞机,是否有顺子,则空间过大。

但由于最后选择中不能有飞机和顺子,所以只有出现了飞机和顺子,最后这种选择一定不符合要求。

故可省掉 $ok2$,$ok3$。

const int maxn = 1000 + 5;
const int maxk = 1500 + 5;	
int dp1[maxn][maxk][2], dp2[maxn][maxk][5][2], dp3[maxn][maxk][5][2], dp4[maxn][maxk][5][5][2];

int dfs1(int pos, int rest, bool ok) {
    if(rest < 0 || pos == -1) return 0;
    if(rest == 0) return ok;
    if(dp1[pos][rest][ok] != -1) return dp1[pos][rest][ok];
    int ans = 0;
    for(int i = 0;i <= 4;i++)
        ans = (ans + dfs1(pos - 1, rest - i, (ok == true || i == 4))) % Mod;
    dp1[pos][rest][ok] = ans;
    return ans;
}

int dfs2(int pos, int rest, int last, bool ok) {
    if(rest < 0 || pos == -1) return 0;
    if(rest == 0) return !ok;
    if(dp2[pos][rest][last][ok] != -1) return dp2[pos][rest][last][ok];
    int ans = 0;
    for(int i = 0;i <= 4;i++)
        ans = (ans + dfs2(pos - 1, rest - i, i, (ok == true || (i >= 3 && last >= 3)))) % Mod;
    dp2[pos][rest][last][ok] = ans;
    return ans;
}

int dfs3(int pos, int rest, int cnt, bool ok)
{
    if(rest < 0 || pos == -1) return 0;
    if(rest == 0) return !ok;
    if(dp3[pos][rest][cnt][ok] != -1) return dp3[pos][rest][cnt][ok];
    int ans = 0;
    for(int i = 0;i <= 4;i++) {
        int k = (i >= 1) ? 1 : -cnt;
        ans = (ans + dfs3(pos - 1, rest - i, cnt + k, (ok == true || cnt + k >=5))) % Mod;
    }
    dp3[pos][rest][cnt][ok] = ans;
    return ans;
}


int dfs4(int pos, int rest, int cnt, int last, bool ok) {
    if(rest < 0 || pos == -1) return 0;
    if(rest == 0) return ok;
    if(dp4[pos][rest][cnt][last][ok] != -1) return dp4[pos][rest][cnt][last][ok];
    int ans = 0;
    for(int i = 0;i <= 4;i++) {
        int k = (i >= 1) ? 1 : -cnt;
        if(!(cnt + k >= 5 || (i >= 3 && last >= 3)))  
            ans = (ans + dfs4(pos - 1, rest - i, cnt + k, i, (ok == true || (i == 4)))) % Mod;
    }
    dp4[pos][rest][cnt][last][ok]=ans;
    return ans;
}

int solve(int x, int opt) {
    int top = 0;
    if(opt == 1) {memset(dp1, -1, sizeof(dp1)); return dfs1(x, x / 3 * 4, false);}
    if(opt == 2) {memset(dp2, -1, sizeof(dp2)); return dfs2(x, x / 3 * 4, -1, false);}
    if(opt == 3) {memset(dp3, -1, sizeof(dp3)); return dfs3(x, x / 3 * 4, 0, false);}
    if(opt == 4) {memset(dp4, -1, sizeof(dp4)); return dfs4(x, x / 3 * 4, 0, -1, false);}
}

P3413 SAC#1 - 萌数

可以用所有数减去不含回文子串的个数。

那么如何判断是否有回文子串?

因为一个回文串,必定中间的$2$位或$3$位回文,那么如果一个数的任意连续$3$位都不一样,则不是回文串。

定义状态为 $dp[pos][num1][num2]$ 表示当前位为 $pos$,$pos+1$ 位为 $num1$,$pos+2$ 位为 $num2$。

答案可能会很大,一些优化:

const int maxn = 1000+5;
int a[maxn];
char l[maxn], r[maxn];
ll dp[maxn][10][10];

ll dfs(int pos, int num1, int num2, bool lead, bool limit) {
    if(pos == 0) return 1;
    if(!limit && !lead && num1 != -1 && num2 != -1 && dp[pos][num1][num2] != -1) return dp[pos][num1][num2];
    int up;
    if(!limit) up = 9;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        if(lead == true) {
            if(i == 0) ans = (ans + dfs(pos - 1, -1, -1, true, (limit == true && i == a[pos]))) % Mod;
            else ans = (ans + dfs(pos - 1, i, -1, false, (limit == true && i == a[pos]))) % Mod;
        }
        else if(i != num1 && i != num2) ans = (ans + dfs(pos - 1, i, num1, false, (limit == true && i == a[pos]))) % Mod;
    }
    if(!limit && !lead && num1 != -1 && num2 != -1)
        dp[pos][num1][num2] = ans;
    return ans;
}

ll solve(char num[]) {
    memset(dp, -1, sizeof(dp));
    int len = strlen(num + 1);
    for(int i = 1;i <= len;i++) a[len - i + 1] = num[i] - '0';
    return dfs(len, -1, -1, true, true);
}

int main() {
    cin >> (l + 1) >> (r + 1);
    ll numl = 0, numr = 0, len;
    for(int i = 1;i <= strlen(l + 1);i++)
        numl = (numl * 10 + l[i] - '0') % Mod;
    for(int i = 1;i <= strlen(r + 1);i++)
        numr = (numr * 10 + r[i] - '0') % Mod;
    bool ok = true;
    for(int i = 2;i <= strlen(l + 1);i++)
        if(l[i] == l[i-1] || l[i] == l[i-2])
            ok = false;
    len = (numr - numl + 1 + Mod) % Mod;
    cout << (len - (solve(r) - solve(l) + ok) + Mod) % Mod << endl;
    return 0;
}

P3303 [SDOI2013]淘金

黑题数位dp,但其实还是比较简单的

由于 $f(x)$ 是 $x$ 的各位数字相乘,则我们可以统计每个数的$0\sim9$的个数,并且也能记忆化。

状态 $dp[pos][num1][num2][num3][num4][num5][num6][num7][num8][num9]$ 表示当前位为 $pos$,$1\sim9$ 各用了 $num_1 \sim num_9$ 次的数的个数。

由于 $f(x)=0$ 不在坐标轴范围内,则在搜索时判断即可。

然后愉快的发现: $N \le 10^{12}$。明显爆炸。

有没有方法优化呢?

后来想到:

  • 一个数位$9$等价于两个数位$3$
  • 一个数位$8$等价于三个数位$2$
  • 一个数位$6$等价于一个数位$2$和一个数位$3$
  • 一个数位$4$等价于两个数位$2$
  • 数位$1$不会对 $f(x)$ 做出贡献

那么我们就可以将 $num4$,$num6$,$num8$,$num9$ 转化为 $num2$ 与 $num3$。并将 $num1$ 删除。

状态转化为 $dp[pos][num2][num3][num5][num7]$

$13^{10} \rightarrow 13\times 39\times 26\times 13\times 13$

现在我们就有了最终所有的 $f(x)$,但答案是二维的,并且让你取前 $k$ 大的和。

二维可以直接用 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n num_{f_i}\times num_{f_j}$ 得到,那么如何统计答案?

可以二分答案一个 $mid$,看有多少个值 $\ge mid$,最终找到恰好有 $k$ 个的情况即可。

注意:本题居然爆long long了,使用了一下__int128

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll min(ll a, ll b) {return a < b ? a : b;}
inline ll max(ll a, ll b) {return a > b ? a : b;}
inline ll abs(ll x) {return x > 0 ? x : -x;}
const int Mod = 1000000007;
const int maxn = 15;
const int maxlen = 40 * 27 * 14 * 14 + 5;
int a[maxn], top, len;
ll n, k, dp[maxn][3 * maxn][2 * maxn][maxn][maxn], maxnum;
__int128 num[maxlen], sum[maxlen];

ll dfs(int pos, int num2, int num3, int num5, int num7, bool lead, bool limit) {
    if(pos == 0) return (num2 + num3 + num5 + num7 + lead == 0);
    if(!limit && !lead && dp[pos][num2][num3][num5][num7] != -1) return dp[pos][num2][num3][num5][num7];
    int up;
    if(!limit) up = 9;
    else up = a[pos];
    ll ans = 0;
    for(int i = 0;i <= up;i++) {
        if(i == 0 && lead == true) ans += dfs(pos - 1, num2, num3, num5, num7, true, (limit == true && i == a[pos])); 
        if(i == 1) ans += dfs(pos - 1, num2, num3, num5, num7, false, (limit == true && i == a[pos]));
        if(i == 2 && num2 >= 1) ans += dfs(pos - 1, num2 - 1, num3, num5, num7, false, (limit == true && i == a[pos]));
        if(i == 3 && num3 >= 1) ans += dfs(pos - 1,num2, num3 - 1, num5, num7, false, (limit == true && i == a[pos]));
        if(i == 4 && num2 >= 2) ans += dfs(pos - 1, num2 - 2, num3, num5, num7, false, (limit == true && i == a[pos]));
        if(i == 5 && num5 >= 1) ans += dfs(pos - 1, num2, num3, num5 - 1, num7, false, (limit == true && i == a[pos]));
        if(i == 6 && num2 >= 1 && num3 >= 1) ans += dfs(pos - 1, num2 - 1, num3 - 1, num5, num7, false, (limit == true && i == a[pos]));
        if(i == 7 && num7 >= 1) ans += dfs(pos - 1, num2, num3, num5, num7 - 1, false, (limit == true && i == a[pos]));
        if(i == 8 && num2 >= 3) ans += dfs(pos - 1, num2 - 3, num3, num5, num7, false, (limit == true && i == a[pos]));
        if(i == 9 && num3 >= 2) ans += dfs(pos - 1, num2, num3 - 2, num5, num7, false, (limit == true && i == a[pos]));
    }
    if(!limit && !lead) 
        dp[pos][num2][num3][num5][num7] = ans;
    return ans;
}

void solve(int num2,int num3,int num5,int num7) {
    ll ans = dfs(top, num2, num3, num5, num7, true, true);
    num[++len] = ans;
    maxnum = max(maxnum, ans);
}

void split(ll x) {
    while(x != 0) {
        a[++top] = x % 10;
        x /= 10;
    }
}

void write(__int128 x) {
    if(!x) return;
    if(x < 0) putchar('-'), x = -x;
    write(x / 10);
    putchar(x % 10 + '0');
}


bool check(__int128 x) {
    int tot = 0;
    for(int i = len, tag = 1;i >= 1 && tag <= len;i--) {
        while(tag <= len && num[i] * num[tag] < x) tag++;
        tot += len - tag + 1;
    }
    return tot < k;
}

int main() {
    scanf("%lld%lld", &n, &k);
    split(n);
    memset(dp, -1, sizeof(dp));
    for(int num2 = 0;num2 <= 39;num2++)
        for(int num3 = 0;num3 <= 26;num3++)
            for(int num5 = 0;num5 <= 13;num5++)
                for(int num7 = 0;num7 <= 13;num7++)	
                    solve(num2, num3, num5, num7);
    sort(num + 1, num + len + 1);
    __int128 l = 0,r = __int128(maxnum) * maxnum, mid, val;
    while(l < r) {
        mid = (l + r) >> 1;
        if(check(mid) == true) r = mid;
        else l = mid + 1;
    }
    val = l - 1;
    for(int i = len;i >= 1;i--) sum[i] = (sum[i+1] + num[i]) % Mod;
    ll ans = 0, cnt = 0;
    for(int i = 1;i <= len;i++) {
        int id = lower_bound(num + 1, num + len + 1, ceil(1.0 * val / num[i])) - num;
        ans = (ans + num[i] % Mod * sum[id]) % Mod;
        cnt += (len - id + 1);
    }
    if(cnt > k) ans = ((ans - val % Mod * (cnt - k) % Mod) + Mod) % Mod;
    printf("%lld\n", ans);
    return 0;
}

总结&吐槽

总的来说,数位dp可以直接套用记忆化模板,考虑好状态设计就行了,所以我认为还是一个简单的dp类型。

费了一下午的时间终于把坑给补上了,电脑都没电了qwq

还有两周就小中考和学校期末考试了,可能暑假之前就不能更新新的文章了,不过2021年目标还是会更新的。

顺便安排一下接下来学习笔记的内容:

  1. 树链剖分
  2. 可持久化系列

大概就是这样了,最后祝大家的小中考能有一个完美的成绩~