51nod-1009-数位dp

一时失言乱红尘 2022-07-15 14:10 253阅读 0赞

题目链接：[51nod1009][]

[1009 数字1的数量][51nod1009] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 5  [难度：1级算法题][1]

![star.png][] 收藏

![plus.png][] 关注

给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。

例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

Input

输入N(1 <= N <= 10^9)

Output

输出包含1的个数

Input示例

Output示例

题目意思：给你一个数n求1-n中所有1的个数，，具体见题目描述

题目思路： （第一次写数位dp，，之前看过别人怎么写，这次自己总算是写出来了，，，好菜啊） dp \[i\] \[j\] 表示从1到以j开头的 i 位数的1的个数 例如 dp \[2\]\[2\] 就表示 1 - 29的1的个数  dp \[5\]\[2\] 就表示1-29999 的1的个数 ，，，那么不难推出转移方程为 dp \[i\] \[j\] = dp \[i\] \[j-1\] + dp \[i-1\] \[9\] ,,,当j=1 时 dp \[i\] \[j\] 要加上 10^(i-1)

还有就是 dp \[i\]  \[0\]  = dp \[i-1\]\[9\]+1; 这个方程可以自己去模拟模拟，还是不难得出的，，，最后求得时候就是按位来求，，把n拆分成 1位的数 + 2位的数+ ....+n的位数的数

然后就是把没位的答案加起来，，，例如  1234  拆分成 1000  + 200 + 30 +4  所以就等于dp \[1\]\[3\] +dp \[2\] \[2\] +(dp \[4\] \[0\] +n-1000) (这里是开头为1的话就要加上后面位数的数)

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    int dp[10][10];
    void init()
    {
        memset(dp,0,sizeof(dp));
        int num=1;
        for(int i=1; i<=9; i++)
        {
            dp[i][0]=dp[i-1][9]+1; //处理以0开头
            for(int j=1; j<=9; j++)
            {
                dp[i][j]=dp[i][j-1]+dp[i-1][9]; //转移方程
                if(j==1)
                {
                    dp[i][j]+=num-1; //以1开头的数
                }
            }
            num*=10;
        }
    }
    int main()
    {
        init();
        int n;cin>>n;
        int num=0; //记录位数
        int m=n;
        while(m)   //统计位数
        {
            num++;
            m/=10;
        }
        m=1;
        int ans=0;
        for(int i=1; i<num; i++)
            m*=10;
        while(num)
        {
            int x=n/m;
            if(x)
            {
                ans+=dp[num][x-1]; //每个位数的答案相加
                if(x==1)
                {
                    ans+=(n-x*m); //以1开头的情况
                }
            }
            num--;
            n-=(m*x); //得到下一位数
            m/=10;
        }
        cout<<ans<<endl;
        return 0;
    }

[51nod1009]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1009
[ok.png]: https://file.51nod.com/images/icon/ok.png
[1]: https://www.51nod.com/onlineJudge/problemList.html#!groupId=2
[star.png]: https://file.51nod.com/images/icon/star.png
[plus.png]: https://file.51nod.com/images/icon/plus.png