poj 2282 數位dp

數位dp，dp[i][j]表示長度為1到i的數字中一共有多少個j，然後按位統計。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int dp[10][10];

int pow(int a,int b)
{
    int ret=1;
    for(int i=1;i<=b;i++)
    ret*=a;
    return ret;
}

long long solve(int a,int tmp)
{
    int s[11],lon=0;
    while(a)
    {
        s[++lon]=a%10;
        a/=10;
    }
    s[0]=0;
    long long ans=0;
    int cnt=0;
    for(int i=lon;i>=1;i--)
    {
        if(tmp==0&&i==lon)
        {
            ans+=dp[i-1][tmp]*(s[i]-1);
            int ff=1*pow(10,i-1)-1;
            ans+=solve(ff,0);
        }
        else
        ans+=dp[i-1][tmp]*s[i];

        ans+=cnt*pow(10,i-1)*s[i];

        if(tmp)
        {
            if(s[i]>tmp) ans+=pow(10,i-1);
            if(s[i]==tmp) cnt++;
        }
        else if(i!=lon)
        {
            if(s[i]>tmp) ans+=pow(10,i-1);
            if(s[i]==tmp) cnt++;
        }
    }
    return ans+cnt;
}

int main()
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=9;i++)
    {
        for(int j=0;j<=9;j++)
        dp[i][j]=dp[i-1][j]*10+pow(10,i-1);
    }
    int a,b;
    while(scanf("%d %d",&a,&b),a||b)
    {
        if(a>b) swap(a,b);
        for(int i=0;i<=9;i++)
        {
            printf("%lld ",solve(b,i)-solve(a-1,i));
        }
        printf("\n");
    }
    return 0;
}