light oj 1205(数位DP)

题目描述：

求给定区间中的回文数有多少个？

首先明确一点，如果一个数是回文数，那么给这个数两边加上相同的数，那么这个数还是回文数。

根据这点就可以进行递推了，p[start][end]=9*p[start+1][end-1](start位不为0)+p[start-1][end](start位为0)；

在设计dfs的时候，由于回文数是对称的，所以只需要一个变量cur(cur>mid)就可以表示从cur到cur对称的位置的回文数的个数；

d[start][cur]表示从start位到cur位时,回文数的个数。

这句话隐含的意思是最高位为start，枚举到第cur位，由于是回文数，所以当cur>mid时，[cur,start]位确定，他们的对称位[1,start+1-cur]也就确定了，

还需枚举[cur,mid]这些位；当cur=mid时任意枚举，对回文数没有影响，当cur<mid时，由于是回文数，已经确定了，不需枚举。

再增加一维表示当前枚举的数字是不是回文数(([start,cur]位是否为回文数);

d[start][cur][state]表示从start位到cur位时,状态为state时回文数的个数。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

#define LL long long

LL n,m;

LL d[][][];

int digit[];

int num[];

LL dfs(int start,int cur,int Zero,int state,bool fp)

{

    if(!cur)

        return state;

    if(!fp && d[start][cur][state]!= -)

        return d[start][cur][state];

    LL ret =  ;int  fpmax = fp ? digit[cur] : ;

    for(int i=;i<=fpmax;i++)

    {

        if( (Zero &&(i==)) )

            ret+=dfs(start-,cur-,Zero&&(i==),state, fp&& i==fpmax);

        else

        {

            num[cur]=i;

            if( (start & )== )

            {

                int mid=((start+)>>);

                if(cur== mid)

                {

                    ret+=dfs(start,cur-,,state,fp&& i==fpmax);

                }

                else if(cur < mid )

                {

                    ret+=dfs(start,cur-,,state&& (num[mid*-cur]==i),fp&& i==fpmax);

                }

                else if(cur>mid)

                {

                    ret+=dfs(start,cur-,,state,fp&& i==fpmax);

                }

            }

            else

            {

                int mid=(start>>)+;

                if(cur<mid)

                {

                   ret+=dfs(start,cur-,,state&& (num[start+-cur]==i),fp&& i==fpmax);

                }

                else

                {

                   ret+=dfs(start,cur-,,state,fp&& i==fpmax);

                }

            }

        }

    }

    if(!fp)  //如果是前缀，当前得到的ret的值，就不能代表dp[len][state]的值

        d[start][cur][state] = ret;

    return ret;

}

LL f(LL n)

{

    int len = ;

    if(n==-)

        return ;

    while(n)

    {

        digit[++len] = n % ;

        n /= ;

    }

    LL answer=dfs(len,len,,,true);

    return answer;

}

void init()

{

    memset(d,-,sizeof(d));

}

int main()

{

    //  freopen("test.txt","r",stdin);

      int t;

      scanf("%d",&t);

      int Case=;

      while(t--)

      {

        scanf("%lld%lld",&n,&m);

        init();

        if(n>m)

            swap(n,m);

        printf("Case %d: %lld\n",++Case,f(m)-f(n-));

      }

      return ;

}

巴特西

light oj 1205(数位DP)

最新文章

热门文章