数位DP。。。。

Palindromic Numbers Time Limit: 2000MS Memory Limit: 32768KB 64bit IO Format: %lld & %llu [Submit]   [Go Back]   [Status] Description 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 4 1 10 100 1 1 1000 1 10000 Sample Output Case 1: 9 Case 2: 18 Case 3: 108 Case 4: 198 Source Problem Setter: Jane Alam Jan [Submit]   [Go Back]   [Status]

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long int LL;

int a[70];

LL dp[70][70];

LL dfs(int len,int l,int r,bool limit,bool ok)

{

	if(l<r) return !limit||(limit&&ok);

	if(!limit&&~dp[len][l])

		return dp[len][l];

	LL ret=0;

	int mx=limit?a[l]:9;

	for(int i=0;i<=mx;i++)

	{

		if(l==len-1&&i==0)

			continue;

		int g=ok;

		if(g) g=a[r]>=i;

		else g=a[r]>i;

		ret+=dfs(len,l-1,r+1,limit&&i==mx,g);

	}

	if(!limit)

		dp[len][l]=ret;

	return ret;

}

LL gaoit(LL n)

{

	if(n<0) return 0;

	if(n==0) return 1;

	int len=0;

	while(n){a[len++]=n%10;n/=10;}

	LL ret=1;

	for(int i=len;i>=1;i--)

		ret+=dfs(i,i-1,0,i==len,1);

	return ret;

}

int main()

{

	int T_T,cas=1;

	cin>>T_T;

	memset(dp,-1,sizeof(dp));

	while(T_T--)

	{

		LL x,y;

		cin>>x>>y;

		if(x>y) swap(x,y);

		printf("Case %d: %lld\n",cas++,gaoit(y)-gaoit(x-1));

	}

	return 0;

}