light 1205

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1205

题解：这题作为一个数位dp，是需要咚咚脑子想想的。这个数位dp方程可能不是很好想到，由于回文串的性质肯定要考虑到对称方面，那么不妨设dp[len][sta][flag]

表示len到sta这些字符串是否能构成回文。这里的数位dp有些特殊由于要考虑到回文的性质会涉及到回朔具体看一下代码。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int dig[20] , now_dig[20];
ll dp[20][20][2];
ll dfs(int len , int sta , int flag , int first) {
    if(len == 0) return (ll)flag;
    if(dp[len][sta][flag] != -1 && !first) return dp[len][sta][flag];
    int t = (first ? dig[len] : 9);
    ll res = 0;
    for(int i = 0 ; i <= t ; i++) {
        now_dig[len] = i;
        if(!i && len == sta) {
            res += dfs(len - 1 , sta - 1 , flag , first && i == t);
        }
        else if(flag && len <= (sta + 1) / 2) {
            res += dfs(len - 1 , sta , i == now_dig[sta - len + 1] , first && i == t);
        }
        else {
            res += dfs(len - 1 , sta , flag , first && i == t);
        }
    }
    if(!first) dp[len][sta][flag] = res;
    return res;
}
ll getnum(ll x) {
    if(x < 0) return 0;
    if(x == 0) return 1;
    int len = 0;
    while(x) {
        dig[++len] = x % 10;
        x /= 10;
    }
    return dfs(len , len , 1 , 1);
}
int main() {
    int t;
    ll n , m;
    int Case = 0;
    scanf("%d" , &t);
    memset(dp , -1 , sizeof(dp));
    while(t--) {
        scanf("%lld%lld" , &m , &n);
        if(m < n) swap(m , n);
        printf("Case %d: %lld
" , ++Case , getnum(m) - getnum(n - 1));
    }
    return 0;
}