HDU 3709 Balanced Number(数位DP)题解

时间:2022-09-23 09:30:16

思路:

之前想直接开左右两边的数结果爆内存...

枚举每次pivot的位置,然后数位DP,如果sum<0返回0,因为已经小于零说明已经到了pivot右边,继续dfs只会越来越小,且dp数组会炸

注意一下一些细节:dp开long long,注意前导零只能算一次

代码:

#include<iostream>
#include<algorithm>
#define ll long long
const int N = 50000+5;
const int INF = 0x3f3f3f3f;
using namespace std;
int dig[20];
ll dp[20][20][2000];
ll dfs(int pos,int piv,int sum,bool limit){
if(pos == -1) return sum == 0? 1 : 0;
if(sum < 0) return 0;
if(!limit && dp[pos][piv][sum] != -1) return dp[pos][piv][sum];
int top = limit? dig[pos] : 9;
ll ret = 0;
for(int i = 0;i <= top;i++){
int tot;
if(pos > piv){
tot = sum + (pos - piv)*i;
}
else if(pos < piv){
tot = sum - (piv - pos)*i;
}
else{
tot = sum;
}
ret += dfs(pos - 1,piv,tot,limit && i == top);
}
if(!limit) dp[pos][piv][sum] = ret;
return ret;
}
ll solve(ll x){
int pos = 0;
if(x == -1) return 0;
while(x){
dig[pos++] = x % 10;
x /= 10;
}
ll ret = 0;
for(int i = 0;i < pos;i++){
ret += dfs(pos - 1,i,0,true);
}
return ret - pos + 1; //前导零只能算一次
}
int main(){
int T;
ll l,r;
scanf("%d",&T);
while(T--){
memset(dp,-1,sizeof(dp));
scanf("%lld%lld",&l,&r);
printf("%lld\n",solve(r) - solve(l - 1));
}
return 0;
}

HDU 3709 Balanced Number(数位DP)题解的更多相关文章

  1. HDU 3709 Balanced Number &lpar;数位DP&rpar;

    Balanced Number Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) ...

  2. hdu 3709 Balanced Number&lpar;平衡数)--数位dp

    Balanced Number Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) ...

  3. HDU 3709 Balanced Number 求区间内的满足是否平衡的数量 (数位dp)

    平衡数的定义是指,以某位作为支点,此位的左面(数字 * 距离)之和 与右边相等,距离是指某位到支点的距离; 题意:求区间内满足平衡数的数量 : 分析:很好这又是常见的数位dp , 不过不同的是我们这次 ...

  4. HDU - 3709 - Balanced Number(数位DP&rpar;

    链接: https://vjudge.net/problem/HDU-3709 题意: A balanced number is a non-negative integer that can be ...

  5. hdu 5898 odd-even number 数位DP

    传送门:hdu 5898 odd-even number 思路:数位DP,套着数位DP的模板搞一发就可以了不过要注意前导0的处理,dp[pos][pre][status][ze] pos:当前处理的位 ...

  6. HDU 5787 K-wolf Number 数位DP

    K-wolf Number Problem Description   Alice thinks an integer x is a K-wolf number, if every K adjacen ...

  7. HDU 5179 beautiful number 数位dp

    题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5179 bc(中文): http://bestcoder.hdu.edu.cn/contes ...

  8. HDU3709 Balanced Number —— 数位DP

    题目链接:https://vjudge.net/problem/HDU-3709 Balanced Number Time Limit: 10000/5000 MS (Java/Others)     ...

  9. HDU 5898 odd-even number &lpar;数位DP&rpar; -2016 ICPC沈阳赛区网络赛

    题目链接 题意:一个数字,它每个数位上的奇数都形成偶数长度的段,偶数位都形成奇数长度的段他就是好的.问[L , R]的好数个数. 题解:裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的 ...

随机推荐

  1. I&lpar;&rpar; 方法

    I()方法的介绍及使用: http://www.jb51.net/article/51213.htm

  2. Redis多机功能介绍

    Redis多机功能目的:以单台Redis服务器过渡到多台Redis服务器 Redis单机在生产环境中存在的问题 1.内存容量不足 Redis使用内存来存书数据库中的数据,但是对于一台机器来说,硬件的内 ...

  3. Spring Batch的事务– Part 3&colon; 略过和重试

    原文:https://blog.codecentric.de/en/2012/03/transactions-in-spring-batch-part-3-skip-and-retry/ This i ...

  4. JS 动态显示 获取下拉框的多个值

    <script type="text/javascript"> function GetProcessVal(i, t) { document.getElementsB ...

  5. PHP魔术方法

    魔术方法:两个下划线开头的格式. PHP中的魔术方法总结 :__construct, __destruct , __call, __callStatic,__get, __set, __isset, ...

  6. dede从www跟目录迁移,网站空间

    图集缩略图表名dede_uploads                    字段url; 图集文章内部的图片表名dede_addonimages        字段imgurls 频道文章列表的图片 ...

  7. eclipse启动报错

    我的是win64位系统,eclipse,jdk1.8    64位 原因:网上说是jdk和eclipse的版本不一致导致的(32位jdk64位eclipse,或者相反): 解决过程: 安装了jdk1. ...

  8. C&plus;&plus;二维数组、指针、对象数组、对象指针

    项目中用到,随手记一下: 1.二维数组.与指针 创建二维数组指针的方式: a.已知一维的大小 1 int **array=new int *[rows]; 2 (for int i=0;i<ro ...

  9. 【修改密码】Linux下修改Mysql的用户&lpar;root&rpar;的密码

    修改的用户都以root为列.一.拥有原来的myql的root的密码: 方法一:在mysql系统外,使用mysqladmin# mysqladmin -u root -p password " ...

  10. UMI开源项目

    本文主要围绕UMI是什么及其特征.安装应用.模板例子等四个方面内容来讲解UMI,希望能够对初学者有所启发. 一. UMI是什么 UMI是可插拔的企业级反应应用程序框架. 二. 特征 特征