抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

数位dp的一些补充

misaka10032

发布于：Apr 1, 2022
次浏览

test
update！

对于补充问题的想法其实来源于leetcode第286场周赛的第三题,要求求解指定长度的回文数。
当然，这道题本身的解法并不难，只需要从小到大枚举固定长度数的前半部分，然后做一下回文处理就可以了(实际上就是把前半部分复制到后面，注意奇数长度的话要吃掉一位)。贴一个该题的AC代码：虽然感觉写的非常的烂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<int> num;
    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
    int n=queries.size();
    vector<long long> ans;
    for(int i=0;i<n;i++)
    {
        num.clear();
        long long x=queries[i];
        long long d=1;
        for(int i=1;i<=(intLength+1)/2-1;i++)    d=d*10;
        x=x+d-1;
        long long t=x;
        cout<<x<<endl;
        int pos=0;
        while(t!=0)
        {
            pos++;
            num.emplace_back(t%10);
            t=t/10;
        }
        if(pos>=(intLength+1)/2+1)  
        {
            ans.emplace_back(-1);
            continue;
        }
        long long ret=x;
        for(int j=0;j<intLength/2;j++)  
        {
            if(intLength%2!=0)  ret=ret*10+num[j+1];
            else                ret=ret*10+num[j];
        }
        ans.emplace_back(ret);
    }
    return ans;
    }
};

但是我周赛的时候没想到，没想明白前半部分的大小就是回文数的大小。于是我有了一个非常奇怪的想法：二分搜索$[10^n,10^{n+1}-1]$，check$10^n$到$mid$范围内回文数的个数就行了。而统计一个范围内回文数的个数，属于数位dp解决问题的范畴。
但是问题来了，我并不知道如何用数位dp来求回文数。。。
经过简单的雾思考，有了一个数位dp来求解回文数问题的解法，顺便还找到了一道类似的问题：Problem
问题本身其实就是求回文数的个数，不过还需要求解在不同进制下的结果，转换下进制就好，问题主要还是如何求解回文数的个数。
先看段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstring> 
using namespace std;
int num[100];
int temp[100];
long long dp[50][50][2][40];
long long dfs(int pos,int start,int check,int limit,int lead,long long l)
{
    if(pos==0 || start==0)  return check;
    if(limit==0 && lead==0 && dp[pos][start][check][l]!=-1)  return dp[pos][start][check][l];
    int up=l-1;
    if(limit==1)  up=num[start];
    long long ans=0;
    for(int i=0;i<=up;i++)
    {
        if(i==0 && lead==1)  ans=ans+dfs(pos-1,start-1,check,limit && i==up,lead && i==0,l);
        else
        {
            temp[start]=i;
            if(check==1 && start<=(pos+1)/2)   ans=ans+dfs(pos,start-1,temp[pos-start+1]==i && check,limit && i==up,lead && i==0,l);
            else                   ans=ans+dfs(pos,start-1,check,limit && i==up,lead && i==0,l);
        }
    }
    if(limit==0 && lead==0)  dp[pos][start][check][l]=ans;
    return ans;
}
long long solve(long long k,long long x)
{
    int pos=0;
    while(x!=0)
    {
        pos++;
        num[pos]=x%k;
        x=x/k;
    }
    return dfs(pos,pos,1,1,1,k);
}
int main()
{
    int k;
    cin>>k;
    memset(num,0,sizeof(num));
    memset(dp,-1,sizeof(dp));
    memset(temp,0,sizeof(temp));              
    for(int turns=0;turns<k;turns++)
    {
        long long ans=0;
        long long l,r;
        long long left,right;
        scanf("%lld%lld%lld%lld",&l,&r,&left,&right);
        if(l>r)  swap(l,r);
        for(long long i=left;i<=right;i++)
        {
            ans=ans+(r-l+1); 
            ans=ans+(i-1)*(solve(i,r)-solve(i,l-1));
        }
        printf("Case #%d: %lld\n",turns+1,ans);
    }
    return 0;
}

pos表示记录回文的其实位置，start表示当前的枚举数位，check表示判断结果，l表示进制数，其他的参数都是数位dp的常见参数。可以发现，前导零是一定会影响回文的判断的，所以当发现前导零时，pos-1，start-1继续搜；之后利用temp记录枚举的结果，当来到数的前半部分时，根据之前的判断结果和当前位是否符合回文规则即可，即$temp[pos-start+1]==i$。

之后提交，喜提Time Limit Exceeded。
经过了简单的挣扎，去看了其他大佬的解决方法，基本的框架都没有什么变化，只是前导零的判断条件变成了：

1
if(i==0 && pos==start)

减少了前导零标记lead，在同样解决问题的情况下，记录了更多的状态(之前lead==1时没记录的状态)，从而减少了搜索所需的时间。
所以数位dp在解决问题的时候，在保证问题正确解决的前提下，还是需要尽可能的减少一些参数的使用，毕竟数位dp的时间复杂度实际上就是填满这些状态所需的时间。
最后附上完整的AC代码，虽然只是很小范围的改动：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstring> 
using namespace std;
int num[100];
int temp[100];
long long dp[50][50][2][40];
long long dfs(int pos,int start,int check,int limit,long long l)
{
    if(pos==0 || start==0)  return check;
    if(limit==0 && dp[pos][start][check][l]!=-1)  return dp[pos][start][check][l];
    int up=l-1;
    if(limit==1)  up=num[start];
    long long ans=0;
    for(int i=0;i<=up;i++)
    {
        if(i==0 && pos==start)  ans=ans+dfs(pos-1,start-1,check,limit && i==up,l);
        else
        {
            temp[start]=i;
            if(check==1 && start<=(pos+1)/2)   ans=ans+dfs(pos,start-1,temp[pos-start+1]==i && check,limit && i==up,l);
            else                   ans=ans+dfs(pos,start-1,check,limit && i==up,l);
        }
    }
    if(limit==0)  dp[pos][start][check][l]=ans;
    return ans;
}
long long solve(long long k,long long x)
{
    int pos=0;
    while(x!=0)
    {
        pos++;
        num[pos]=x%k;
        x=x/k;
    }
    return dfs(pos,pos,1,1,k);
}
int main()
{
    int k;
    cin>>k;
    memset(num,0,sizeof(num));
    memset(dp,-1,sizeof(dp));
    memset(temp,0,sizeof(temp));              
    for(int turns=0;turns<k;turns++)
    {
        long long ans=0;
        long long l,r;
        long long left,right;
        scanf("%lld%lld%lld%lld",&l,&r,&left,&right);
        if(l>r)  swap(l,r);
        for(long long i=left;i<=right;i++)
        {
            ans=ans+(r-l+1); 
            ans=ans+(i-1)*(solve(i,r)-solve(i,l-1));
        }
        printf("Case #%d: %lld\n",turns+1,ans);
    }
    return 0;
}

end☆~

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://misaka-network10032.github.io/2022/04/01/%E6%95%B0%E4%BD%8Ddp%E7%9A%84%E4%B8%80%E4%BA%9B%E8%A1%A5%E5%85%85/

更新于：Apr 1, 2022

算法

c++

评论