Lightoj1205——Palindromic Numbers（数位dp+回文数）-白红宇

Lightoj1205——Palindromic Numbers（数位dp+回文数）

阅读量：2345 次

发布时间：2019-05-10

本文共 1804 字，大约阅读时间需要 6 分钟。

A palindromic number or numeral palindrome is a ‘symmetrical’ number like 16461 that remains the same when its digits are reversed. In this problem you will be given two integers i j, you have to find the number of palindromic numbers between i and j (inclusive).

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing two integers i j (0 ≤ i, j ≤ 1017).

Output

For each case, print the case number and the total number of palindromic numbers between i and j (inclusive).

Sample Input

1 10

100 1

1 1000

1 10000

Output for Sample Input

Case 1: 9

Case 2: 18

Case 3: 108

Case 4: 198

简单来说就是在一串数字的前一半放各种数字，后一半不仅要放，还得与前面对称位置的数匹配，才能把所需的状态传下去

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 10000005#define Mod 10001using namespace std;int dight[40],tmp[40];long long dp[40][100][100];long long dfs(int start,int pos,int s,bool limit){ if(pos<0) return s; if(!limit&&dp[pos][s][start]!=-1) return dp[pos][s][start]; int end; long long ret=0; if(limit) end=dight[pos]; else end=9; for(int d=0; d<=end; ++d) { tmp[pos]=d; if(start==pos&&d==0) ret+=dfs(start-1,pos-1,s,limit&&d==end); else if(s&&pos<(start+1)/2) ret+=dfs(start,pos-1,tmp[start-pos]==d,limit&&d==end); else ret+=dfs(start,pos-1,s,limit&&d==end); } if(!limit) dp[pos][s][start]=ret; return ret;}long long solve(long long a){ memset(dight,0,sizeof(dight)); int cnt=0; while(a!=0) { dight[cnt++]=a%10; a/=10; } return dfs(cnt-1,cnt-1,1,1);}int main(){ memset(dp,-1,sizeof(dp)); int t,cnt=1; scanf("%d",&t); while(t--) { long long x,y; scanf("%lld%lld",&x,&y); if(x>y) swap(x,y); printf("Case %d: %lld\n",cnt++,solve(y)-solve(x-1)); } return 0;}

转载地址：http://jvcvb.baihongyu.com/

你可能感兴趣的文章