51nod-1009-数位dp-蒲公英云

51nod-1009-数位dp

题目链接：51nod1009

1009 数字1的数量

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

关注

给定一个十进制正整数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;
}