abc387c题解

· · 题解

竟然出了数位动态规划？在第三题？蒟蒻疑惑。

建议查看模版以学习。

我们先来看代码：链接。

看到这道题，显然看出是一道非常典型的数位动态规划。

怎么整？

注意到这题的限制条件变成了枚举每一位的大小不能超过首位，那么我们考虑修改记忆化搜索中的 r 定义。

在模版中，r 是记录上一位的数，那么，我们将这个改成记录开头的数，0 代表没有开头。

修改完这一个定义，我们再看搜素代码。

int dfs(int p,int r,bool z,bool lmt){
    if(p==0)return 1;
    if(!lmt&&f[p][r]>-1)return f[p][r];
    int ans=0,mx=(lmt?c[p]:9);
    for(int i=0;i<=mx;i++){
        if(!z&&i>=r&&r!=0)continue;
        if(z&&i==0)ans+=dfs(p-1,0,1,lmt&&(i==mx));
        else ans+=dfs(p-1,(r==0?i:r),0,lmt&&(i==mx));
    }
    if(!lmt&&!z)f[p][r]=ans;
    return ans;
}
int func(int x){
    memset(f,-1,sizeof(f));
    s=to_string(x);
    n=s.size();
    for(int i=1;i<=n;i++)c[n-i+1]=s[i-1]-'0';
    return dfs(n,0,1,1);
}

首先，我们记搜的精髓就是记忆，这里用 f_{p,r} 代表首位是 r，搜到第 p 位（高往低）的答案。

当然，答案可能为 0，所以要初始化成 -1。

考虑一直用的边界需要限制，加入 lmt 限制。

接着我们转移。

要是某一次数还是 0，z 限制就会是 1，而当已经有数，枚举的 i 超过了首位 r，状态不合法。

要是我们将 0 给他转移到 0 上，即 z=1 且 i=0 时，我们的 r 将保留 0，z 保留 1，lmt 按照模版正常维护。

否则我们要判断第一次让数从 0 变成 i 的情况，如果是，那么 r=i，否则不变。

感觉转移还是浅显易懂。

然后是剩下的。

我们的求解函数应该把开头 r 改成 0，其他跟板子一模一样。

最后放板子和此题来对比下。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
int a,b,c[N],cur,n,f[N][N];
string s;
int dfs(int p,int r,bool z,bool lmt){
    if(p==0)return 1;
    if(!lmt&&f[p][r]>-1)return f[p][r];
    int ans=0,mx=(lmt?c[p]:9);
    for(int i=0;i<=mx;i++){
        if(!z&&abs(i-r)<2)continue;
        if(z&&i==0)ans+=dfs(p-1,i,1,lmt&&(i==mx));
        else ans+=dfs(p-1,i,0,lmt&&(i==mx));
    }
    if(!lmt&&!z)f[p][r]=ans;
    return ans;
}
int func(int x){
    memset(f,-1,sizeof(f));
    s=to_string(x);
    n=s.size();
    for(int i=1;i<=n;i++)c[n-i+1]=s[i-1]-'0';
    return dfs(n,-2,1,1);
}
signed main(){
    cin>>a>>b;
    cout<<func(b)-func(a-1);
    return 0;
}

这题：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
int a,b,c[N],cur,n,f[N][N];
string s;
int dfs(int p,int r,bool z,bool lmt){
    if(p==0)return 1;
    if(!lmt&&f[p][r]>-1)return f[p][r];
    int ans=0,mx=(lmt?c[p]:9);
    for(int i=0;i<=mx;i++){
        if(!z&&i>=r&&r!=0)continue;
        if(z&&i==0)ans+=dfs(p-1,0,1,lmt&&(i==mx));
        else ans+=dfs(p-1,(r==0?i:r),0,lmt&&(i==mx));
    }
    if(!lmt&&!z)f[p][r]=ans;
    return ans;
}
int func(int x){
    memset(f,-1,sizeof(f));
    s=to_string(x);
    n=s.size();
    for(int i=1;i<=n;i++)c[n-i+1]=s[i-1]-'0';
    return dfs(n,0,1,1);
}
signed main(){
    cin>>a>>b;
    cout<<func(b)-func(a-1);
    return 0;
}

是不是很像？