最近在学数位DP， 感觉还是满有收获的！ 做了几个题之后想起来自己OJ上曾经做的一道题，以前是用数学方法写的，现在改用数位DP来写了一遍。
题目：
1255: 数字统计
时间限制: 1 Sec 内存限制: 128 MB
提交: 31 解决: 4
[提交][状态]
题目描述
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，
每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数
字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，
2，…，9。
输入
给出表示书的总页码的整数n（1≤n≤2^31-1）
输出
输出10行，在第k行输出页码中用到数字k-1 的次数，k=1，2，…，10。
样例输入
11
样例输出
1
4
1
1
1
1
1
1
1
1
链接：http://acm.zznu.edu.cn/problem.php?id=1255
数学方法：
其实就是假设每一位是0-9然后进行判断， 计算出结果
#include<stdio.h>
int Slove(int num,int k)
{
int L, R, M, P = , a = num;
int sum = ;
while(a)
{
R = num%P;
M = a%;
L = a/;
if(k)
{
if(k < M)
sum += (L+)*P;
else if(k == M)
sum += L*P + (R+);
else
sum += L*P;
}
else
{
if(a<)
break;
if(k == M)
sum += (L-)*P + (R+);
else
sum += L*P;
}
P *= ;
a /= ; }
return sum;
} int main()
{
int n, ans;
int i;
scanf("%d",&n);
for(i=; i<=; i++)
{
ans = Slove(n,i);
printf("%d\n",ans);
}
return ;
}
数位DP;
这个就比较通用了， 就是套模版， 对数据的处理上 稍加注意， 然后把状态确定好。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL dp[][][][];//dp[位数][数字出现的次数][这个数字是多少][首位是否是0]
int bit[]; LL dfs(int pos,int cou,int num,int flag,bool is0)
{
if( pos == - )
{
return cou;
} if(!flag && dp[pos][cou][num][is0] != -)
return dp[pos][cou][num][is0]; LL ans = ;
int end = flag? bit[pos]: ; for(int i=; i<=end; i++)
{
if(i == num && !(is0 && i == ) )
ans += dfs(pos-, cou+, num, flag && i == end, is0 && i == );
else
ans += dfs(pos-, cou, num, flag && i == end, is0 && i == );
} if(!flag)
dp[pos][cou][num][is0] = ans; return ans;
} void solve(LL n)
{
int len = , i, m = n;
LL ans;
while(n)
{
bit[len++] = n%;
n /= ;
} for(i=; i<=; i++)
{
ans = dfs(len-, , i, , );
printf("%lld\n", ans);
}
// printf("\n\n\n");
} int main()
{
LL a;
memset(dp, - ,sizeof(dp)); while(scanf("%lld", &a) != EOF)
{
solve(a);
}
// printf("\n\n\n");
return ;
}