hdu 6156 Palindrome Function（数位dp）

之前做网络赛的时候，看出来这是数位dp了，奈何自己不会数位dp，网上找了个数位dp计算回文数的模板也套错了 因为不会数位dp，也找不出是哪里的毛病。
现在学了数位dp，再来切这题。
这题和LightOJ 1205 Palindromic Numbers基本一样，就是多了个不同的进制。在lightoj 1205的基础上，再加一维表示不同的进制，然后数位dp即可。做的时候数组开小了，wa了好几发。。查了老半天才发现。。

#include <stdio.h>
#include <string.h>
typedef long long LL;
LL dp[40][40][40];
int digit[35];
int assist[35];

int calc(int num, int k)
{
    int len = 0;
    while(num)
    {
        digit[len++] = num%k;
        num /= k;
    }
    return len;
}

LL dfs(int i, int len, int e, int k)
{
    if(i == -1) return 1;
    if(!e && ~dp[k][len][i]) return dp[k][len][i];
    LL res = 0;
    int u = e?digit[i]:(k-1);
    for(int d = 0; d <= u; ++d)
    {
        assist[i] = d;
        if(i == len && d == 0)
            res += dfs(i-1,len-1,e&&d==u,k);
        else if(i < (len+1)/2 && d == assist[len-i])
            res += dfs(i-1,len,e&&d==u,k);
        else if(i >= (len+1)/2)
            res += dfs(i-1,len,e&&d==u,k);
    }
    return e?res:dp[k][len][i]=res;
}

LL solve(int num, int k)
{
    int len = calc(num,k);
    return dfs(len-1,len-1,1,k);
}

int main()
{
    int T,L,R,l,r,time = 0;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d %d",&L,&R,&l,&r);
        LL num = R-L+1;
        LL res = 0;
        LL cnt = 0;
        for(int i = l; i <= r; ++i)
        {
            cnt = solve(R,i)-solve(L-1,i);
            res = res + num-cnt + cnt*(LL)i;
        }
        printf("Case #%d: %I64d\n",++time,res);
    }
    return 0;
}