Description
The Little Elephant very much loves sums on intervals.
This time he has a pair of integers l and r(l?≤?r). The Little Elephant has to find the number of such integers x(l?≤?x?≤?r), that the first digit of integer x equals the last one (in decimal notation). For example, such numbers as 101, 477474 or 9 will be included in the answer and47, 253 or 1020 will not.
Help him and count the number of described numbers x for a given pair l and r.
Input
The single line contains a pair of integers l and r(1?≤?l?≤?r?≤?1018) — the boundaries of the interval.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.
Output
On a single line print a single integer — the answer to the problem.
Sample Input
2 47
12
47 1024
98
对于统计一个区间类的计数问题可以考虑用数位DP来写。
回到本题就是统计首位相同数字个数。dp[i][j]表示位数为i且首位为j的个数。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int INF = 0x3f3f3f3f;
LL dp[50][10];
int num[50];
LL l,r;
LL dfs(int pos,int st,int ed,int first,int flag)
{
if(pos==0)
return st==ed;
if(!flag&&dp[pos][st]!=-1)
return dp[pos][st];
int d=flag?num[pos]:9;
LL sum=0;
for(int i=0;i<=d;i++)
{
int s=st,e=ed;
if(!first&&i)
s=i;
if(pos==1)
e=i;
sum+=dfs(pos-1,s,e,first||i,flag&&i==d);
}
if(!flag) dp[pos][st]=sum;
return sum;
}
LL solve(LL x)
{
if(x==0) return 1;
int pos=0;
while(x)
{
num[++pos]=x%10;
x/=10;
}
return dfs(pos,0,-1,0,1);
}
int main()
{
CLEAR(dp,-1);
while(~scanf("%lld%lld",&l,&r))
{
LL ans=solve(r)-solve(l-1);
printf("%lld\n",ans);
}
return 0;
}
原文：http://blog.csdn.net/u013582254/article/details/44626687