51nod 1009 数字1的数量 (不用找规律的方法,用数位dp板子写这道题,以加深对数位dp的理解)

时间:2022-12-16 11:38:17

1009 数字1的数量 51nod 1009 数字1的数量 (不用找规律的方法,用数位dp板子写这道题,以加深对数位dp的理解)
基准时间限制: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示例
12
Output示例
5

这道题用找规律,统计每一位上1出现的次数,很简单就能写出来。

https://blog.csdn.net/wyg1997/article/details/52169036 ( 找规律)
http://www.knowsky.com/1046368.html  (数位dp)
这两个博客写的很详细。

既然这道题是数位dp,那么我想了好久怎么用数位dp写这道题,写了三个多小时才写出来,中间还差点放弃。

这道题作为数位dp入门题就过分了吧(可能是我太菜了吧),我数位dp都写了8道题了,这个题依旧想了3个小时,才写出来。(建议数位dp的新手还是先去做 (不要62) 吧)

int dp[pos], //dp[i]表示后i位从0遍历到99999(共i+1个9),能出现多少个1

代码稍微解释了一下,应该能看懂吧

#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <queue>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
typedef long long LL;
const LL mod=1e9+7;
const int M=13;
using namespace std;
const int N =1e5+100;
int a[10],dp[10];//dp[i]表示后i位从0遍历到99999(i+1个9),能出现多少个1
int v[10]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};//存10的平方,立方, 等等
int dfs(int pos,int num,int limit)//num表示从最高位到(pos+1)位出现了多少个1
{
    if(pos==-1) return num;
    if(!limit&&dp[pos]!=-1) return num*v[pos]+dp[pos];
    //如果后dp[pos]已经存的有值了,那么num*(10^(pos+1))直接加上dp[pos];
    int up=limit?a[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++)
        ans+=dfs(pos-1,num+(i==1),limit&&i==up);
    return limit?ans:dp[pos]=ans;
}//其余都是板子
int slove(int x)
{
    int pos=0;//习惯不同,代码就不一样,pos从0开始的
    for(;x;x/=10)
        a[pos++]=x%10;
    return dfs(pos-1,0,1);
}
int main()
{
    mem(dp,-1);
    int n;
    scanf("%d",&n);
    printf("%d\n",slove(n));
}