题目链接：http://lightoj.com/volume_showproblem.php?problem=1205
题意：求[l,r]内回文数的数量。
dp(s,l,ok)表示数字以s为开头，长度为l的时是/不是回文数
dp(s,l,ok)可以由dp(s,l-1,ok)更新来，当且仅当接下来插入的一位与s对应的位置相同。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 22; 6 int digit[maxn], rev[maxn]; 7 LL dp[maxn][maxn][2]; 8 LL l, r; 9 10 LL dfs(int s, int l, bool ok, bool flag) { 11 if(l < 0) return ok; 12 if(!flag && ~dp[s][l][ok]) return dp[s][l][ok]; 13 int pos = flag ? digit[l] : 9; 14 LL ret = 0; 15 for(int i = 0; i <= pos; i++) { 16 rev[l] = i; 17 if(i == 0 && s == l) ret += dfs(s-1, l-1, ok, flag&&(i==pos)); 18 else if(ok && l < (s + 1) / 2) ret += dfs(s, l-1, i==rev[s-l], flag&&(i==pos)); 19 else ret += dfs(s, l-1, ok, flag&&(i==pos)); 20 } 21 if(!flag) dp[s][l][ok] = ret; 22 return ret; 23 } 24 25 LL f(LL x) { 26 int pos = 0; 27 while(x) { 28 digit[pos++] = x % 10; 29 x /= 10; 30 } 31 return dfs(pos-1, pos-1, true, true); 32 } 33 34 int main() { 35 //freopen("in", "r", stdin); 36 int T, _ = 1; 37 scanf("%d", &T); 38 memset(dp, -1, sizeof(dp)); 39 while(T--) { 40 scanf("%lld%lld",&l,&r); 41 if(l > r) swap(l, r); 42 printf("Case %d: %lld ", _++, f(r) - f(l-1)); 43 } 44 return 0; 45 }