非正经解法——数位DP

不会C++的noah

2024-06-25 07:19:39

发布于：浙江

41阅读

0回复

0点赞

本题可以使用数位DP（数位DP见之前的帖子）

代码（非最优解，仅供参考）：

#include <bits/stdc++.h>
using namespace std;
long long a[101],dp[50][50][50][50],len,digit;
long long dfs(int pos,int cnt,bool limit,bool lold){
    long long ans=0;
    if (pos==len){
        return cnt;
    }
    else if (dp[pos][cnt][limit][lold]!=-1){
        return dp[pos][cnt][limit][lold];
    }
    for (int i=0;i<=(limit?a[pos]:9);++i){
        if (lold && i==0){
            ans+=dfs(pos+1,cnt,limit && i==a[pos],1);
        }else{
            ans+=dfs(pos+1,cnt+(i==digit),limit && i==a[pos],0);
        }
    }
    dp[pos][cnt][limit][lold]=ans;
    return ans;
}
long long f(long long x){
    len=0;
    memset(dp,-1,sizeof dp);
    memset(a,0,sizeof a);
    while (x){
        a[len++]=x%10;
        x/=10;
    }
    reverse(a,a+len);
    return dfs(0,0,1,1);
}
int main(){
    long long x,y;
    cin>>x;
    if (x<0){
        x=-x;
    }
    for (int i=0;i<=9;++i){
        digit=i;
        long long l=f(x-1),r=f(x);
        cout<<r-l<<endl;
    }
}

时间复杂度： $O(9 \log{n})$ ,空间复杂度： $O(8 \times 50^4)$

有帮助，赞一个

去预览

0/2000

全部评论 2

dino
这么复杂干什么?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

2024-11-06 来自浙江
0
‮队团加不）ด้้童帅_者仇复
我嘞个蚊子打大炮

2024-06-26 来自广东
0
- 不会C++的noah
  回复‮队团加不）ด้้童帅_者仇复
  这是蚂蚁刀
  
  2024-06-26 来自浙江
  0