hdoj3709（数位dp）

桃扇骨 2021-12-21 01:07 301阅读 0赞

题目链接：https://vjudge.net/problem/HDU-3709

题意：求出\[l,r\]中的平衡数，平衡数即存在一个中心点使得两边的力矩和相等。

思路：首先需要知道一个数最多只有一个中心点，可以通过反证法轻松得出，所以我们可以对长为pos的数枚举其中心点。用dp\[pos\]\[m\]\[sum\]表示长为pos+1、中心点在第m位、现在的力矩和为sum的数的个数。中心点一边的力矩和最大大约为1500，所以离散化一下，用1500表示0。另外要注意的是每次枚举中心点都会将0算入，所以最后要减取多加的pos-1个0。

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long LL;
    
    const int key=1500;
    int T;
    LL a[20],dp[20][20][2*key];
    
    LL dfs(int pos,int m,int sum,bool limit){
        if(pos==-1) return sum==key;
        if(!limit&&dp[pos][m][sum]!=-1) return dp[pos][m][sum];
        int up=limit?a[pos]:9;
        LL tmp=0;
        for(int i=0;i<=up;++i)
            tmp+=dfs(pos-1,m,sum+i*(pos-m),limit&&i==a[pos]);
        if(!limit) dp[pos][m][sum]=tmp;
        return tmp;
    }
    
    LL solve(LL x){
        int pos=0;
        LL ans=0;
        while(x){
            a[pos++]=x%10;
            x/=10;
        }
        for(int i=0;i<pos;++i)
            ans+=dfs(pos-1,i,key,true);
        return ans-pos+1;
    }
    
    int main(){
        memset(dp,-1,sizeof(dp));
        scanf("%d",&T);
        while(T--){
            LL l,r;
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",solve(r)-solve(l-1));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/10765159.html

发表评论取消回复

表情：

评论列表（有 0 条评论，301人围观）

还没有评论，来说两句吧...

相关阅读

相关数位DP 详解

序 > 天堂在左，战士向右引言数位DP在竞赛中的出现几率极低，但是如果不会数位DP，一旦考到就只能暴力骗分。以下是数位DP详解，涉及到的例题有：

叁歲伎倆/ 2023年08月17日 17:38/ 0 赞/ 140 阅读

相关数位dp小结

数位dp小结关于limit的问题在数位dp中,limit的作用主要有两个。控制枚举的界限，倘若没有界限，每一位的枚举范围都是0-9. 但如果有界限，

桃扇骨/ 2023年07月03日 07:22/ 0 赞/ 20 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 226 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 202 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 310 阅读

相关 HDU-3709 Balanced Number(数位DP)

超、凢脫俗/ 2022年06月09日 00:27/ 0 赞/ 175 阅读

相关 hdu 3709 数字dp（小思）

[http://acm.hdu.edu.cn/showproblem.php?pid=3709][http_acm.hdu.edu.cn_showproblem.php_pid

怼烎@/ 2022年03月27日 09:52/ 0 赞/ 188 阅读

相关 hdoj3709（数位dp）

题目链接：https://vjudge.net/problem/HDU-3709 题意：求出\[l,r\]中的平衡数，平衡数即存在一个中心点使得两边的力矩和相等。思路：首

桃扇骨/ 2021年12月21日 01:07/ 0 赞/ 302 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 305 阅读

相关数位DP模板

int a[20]; ll dp[20][state]; ll dfs(int pos,/state变量/,bool lead/前导零/,bool li

左手的ㄟ右手/ 2021年09月19日 05:42/ 0 赞/ 371 阅读