題意：給定范圍內是回文數的個數。
思路：
dp[site][len] site位的回文長度是len。
需要一個負責數組 ok存每位放的數。
然後就是dfs了，就是取len 的中間值mid
超過mid的話 就看看ok裡面之前對稱的那個數 判斷是否相等
相等才能放進入下一位。
注意判斷前導0，和這個oj必須用long long。
代碼：
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
using namespace std;
//2014年9月24日10:30:25
long long dp[22][22];
int num[22],ok[22];
long long dfs(int site,int n,int zero,int f)
{
if(site==0) return 1;
if(!f&&!zero&&dp[site][n]!=-1) return dp[site][n];
int len=f?num[site]:9;
long long ans=0;
for(int i=0; i<=len; i++)
{
if(zero)
{
if(i==0) ans+=dfs(site-1,n-1,zero&&i==0,f&&i==len);
else
{
ok[site]=i;
ans+=dfs(site-1,n,zero&&i==0,f&&i==len);
}
}
else
{
int mid=(n+1)/2;
if(n%2)
{
if(site==mid) ans+=dfs(site-1,n,zero&&i==0,f&&i==len);
else if(site>mid)
{
ok[site]=i;
ans+=dfs(site-1,n,zero&&i==0,f&&i==len);
}
else
{
if(ok[n+1-site]==i) ans+=dfs(site-1,n,zero&&i==0,f&&i==len);
}
}
else
{
if(site>mid)
{
ok[site]=i;
ans+=dfs(site-1,n,zero&&i==0,f&&i==len);
}
else
{
if(ok[n+1-site]==i) ans+=dfs(site-1,n,zero&&i==0,f&&i==len);
}
}
}
}
if(!f&&!zero) dp[site][n]=ans;
return ans;
}
long long solve(long long x)
{
int cnt=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
return dfs(cnt,cnt,1,1);
}
int main()
{
int t,cas=1;
cin>>t;
memset(dp,-1,sizeof(dp));
while(t--)
{
long long x,y;
scanf("%lld%lld",&x,&y);
if(x>y) swap(x,y);
printf("Case %d: %lld\n",cas++,solve(y)-solve(x-1));
}
return 0;
}
//2014年9月24日11:26:45
