poj 3286 How many 0's? --- 数位dp

找找规律就可以

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

ll a[12]={1LL,10LL,100LL,1000LL,10000LL,100000LL,1000000LL,10000000LL,100000000LL,1000000000LL,10000000000LL,100000000000LL};

ll cal(ll n)
{
    ll ans=0,left,tmp;
    for(int i=1;i<12;i++)
    {
        left=n/a[i]-1;
        ans+=left*a[i-1];
        tmp=(n%a[i]-n%a[i-1])/a[i-1];
        if(tmp>0) ans+=a[i-1];
        else if(tmp==0) ans+=n%a[i-1]+1;
        if(n<a[i]) break;
    }
    return ans;
}


int main()
{
    ll n,m;
    while(scanf("%I64d%I64d",&n,&m)&&m>=0)
    {
        printf("%I64d\n",cal(m)-cal(n-1));
    }
    return 0;
}

poj 3286 How many 0's? --- 数位dp

原文：http://blog.csdn.net/u011032846/article/details/18823773