HDU 6156 Palindrome Function（数位DP）题解

思路：

数位dp的操作是dfs+记忆化，我们dp开四维：位置，长度，进制，是否回文。然后每次暴搜记录下每个位置的数字是什么，搜到对称轴另一边需要检查是否符合回文。

终于把友谊赛的题目都补完了...没做出来的都是学过的，做出来的都是没学过骚操作过的...学以不致用...

代码：

#include<cstdio>

#include<set>

#include<stack>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = 1000+5;

const int INF = 0x3f3f3f3f;

ll dp[40][40][40][2];

int bit[100],num[100];

ll dfs(int pos,int len,int k,int sta,bool limit){

    if(pos < 0) return sta? k : 1;

    if(!limit && dp[pos][len][k][sta] != -1) return dp[pos][len][k][sta];

    int top = limit? bit[pos] : (k - 1);

    ll ret = 0;

    for(int i = 0;i <= top;i++){

        num[pos] = i;

        if(i == 0 && pos == len){   //前导〇

            ret += dfs(pos - 1,len - 1,k,sta,limit && i == top);

        }

        else if(sta && pos < (len + 1)/2){

                ret += dfs(pos - 1,len,k,i == num[len - pos],limit && i == top);

        }

        else{

            ret += dfs(pos - 1,len,k,sta,limit && i == top);

        }

    }

    if(!limit) dp[pos][len][k][sta] = ret;

    return ret;

}

ll solve(int x,int k){

    int pos = 0;

    while(x){

        bit[pos++] = x % k;

        x /= k;

    }

    return dfs(pos - 1,pos - 1,k,1,true);

}

int main(){

    int T,Case = 1;

    int L,R,l,r;

    scanf("%d",&T);

    memset(dp,-1,sizeof(dp));

    while(T--){

        ll ans = 0;

        scanf("%d%d%d%d",&L,&R,&l,&r);

        for(int j = l;j <= r;j++){

            ans += solve(R,j) - solve(L - 1,j);

        }

        printf("Case #%d: %lld\n",Case++,ans);

    }

    return 0;

}

巴特西

HDU 6156 Palindrome Function（数位DP）题解

最新文章

热门文章