做的时候毫无思路。 思路参考的：http://blog.csdn.net/harlow_cheng/article/details/77466732 代码参考的：http://blog.csdn.net/u010660276/article/details/46554067 他们是用的三维数组，dp[start][pos][state]，表示从第start位开始搜索，即这个回文数的长度为start+1，当前枚举到第pos位，state表示当前状态之前的那个状态是否合法。 我看了看，感觉state有点多余，因为是回文数，只要有一位不对称，就不可能组成回文数，那么state这个状态就可以去掉，我们只对可行的状态进行搜索，不可行的忽略掉就好。那数组就变成了dp[start][pos],即从高位开始，从第start位开始搜索，一直搜索到最低位，start位即第一个不为0的位置，start+1也就是这个回文数的长度。回文数第一位不能为0，那个start也就是用来处理前导0的。
#include <stdio.h> #include <string.h> typedef long long LL; int digit[20]; int assist[20]; int dp[20][20]; template<typename T> void swap(T &a, T &b) { a = a^b; b = a^b; a = a^b; } int calc(LL num) { int len = 0; while(num) { digit[len++] = num; num /= 10; } return len; } LL dfs(int i, int len, int e) { if(i == -1) return 1; if(!e && ~dp[len][i]) return dp[len][i]; LL res = 0; int u = e?digit[i]:9; for(int d = 0; d <= u; ++d) { assist[i] = d; if(d == 0 && len == i) res += dfs(i-1,len-1,e&&d==u); else if(i<(len+1)/2 && d==assist[len-i]) res += dfs(i-1,len,e&&d==u); else if(i>=(len+1)/2) res += dfs(i-1,len,e&&d==u); } return e?res:dp[len][i]=res; } LL solve(LL num) { int len = calc(num); return dfs(len-1,len-1,1); } int main() { int T,time = 0; LL a,b; memset(dp,-1,sizeof(dp)); scanf("%d",&T); while(T--) { scanf("%lld %lld",&a,&b); if(a > b) swap(a,b); printf("Case %d: %lld\n",++time,solve(b)-solve(a-1)); } return 0; }