动态规划学习系列——数位DP（练手二）

题目链接：BZOJ 1833

解题思路：
非常常规的一道数位DP题目，然而，因为好久没做过题，结果怒调了三个钟。关键的地方在于数字0的处理，我采用的做法是先不考虑特殊的0，处理完别的数字之后，使用直接推公式的方法直接求得0的个数。注意数据范围，得使用long long。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

long long dp[20][15][15],tmp[20],cnt,ans[15],ans1[15];

void cal(long long num)
{
    memset(tmp,0,sizeof(tmp));
    cnt=0;
    while(num)
    {
        tmp[cnt++]=num%10;
        num/=10;
    }
}

void sol(long long n)
{
    cal(n);
    memset(dp,0,sizeof(dp));
    for(int i=0;i<10;i++)
        dp[1][i][i]=1;

    for(int i=2;i<=cnt;i++)
        for(int j=0;j<10;j++)
        {
            for(int k=0;k<10;k++)
                for(int l=0;l<10;l++)
                    dp[i][j][l]+=dp[i-1][k][l];
            dp[i][j][j]+=(long long)(pow(10,i-1)+0.5);
        }
}

void solve(long long a,long long b)
{
    memset(ans,0,sizeof(ans));
    memset(ans1,0,sizeof(ans1));
    sol(b);         
    for(int i=cnt-1;i>=0;i--)
    {
        for(int j=0;j<tmp[i];j++)
            for(int k=0;k<10;k++)
                ans[k]+=dp[i+1][j][k];
        if(i>0)
        {
            for(int j=cnt-1;j>=i;j--)
                ans[tmp[j]]+=tmp[i-1]*((long long)(pow(10,i-1)+0.5));
        }
    }
    for(int i=0;i<cnt;i++)
        ans[tmp[i]]++;
    ans[0]=0;
    for(long long i=1;i<=b;i*=10)
    {
        ans[0]+=b/(i*10)*i;
        if(b%(i*10)/i==0)
            ans[0]-=(i-b%i-1);
    }

    //同前半段
    sol(a);         
    for(int i=cnt-1;i>=0;i--)
    {
        for(int j=0;j<tmp[i];j++)
            for(int k=0;k<10;k++)
                ans1[k]+=dp[i+1][j][k];
        if(i>0)
        {
            for(int j=cnt-1;j>=i;j--)
                ans1[tmp[j]]+=tmp[i-1]*((long long)(pow(10,i-1)+0.5));
        }
    }
    for(int i=0;i<cnt;i++)
        ans1[tmp[i]]++;
    ans1[0]=0;
    for(long long i=1;i<=a;i*=10)
    {
        ans1[0]+=a/(i*10)*i;
        if(a%(i*10)/i==0)
            ans1[0]-=(i-a%i-1);
    }   
    for(int i=0;i<10;i++)
        ans[i]-=ans1[i];
}

int main()
{
    long long a,b;
    while(~scanf("%lld %lld",&a,&b))
    {
        solve(a-1,b);       
        printf("%lld",ans[0]);
        for(int i=1;i<10;i++)
            printf(" %lld",ans[i]);
        printf("\n");
    }   

    return 0;
}