思路:
之前想直接开左右两边的数结果爆内存...
枚举每次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)题解的更多相关文章
-
HDU 3709 Balanced Number (数位DP)
Balanced Number Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) ...
-
hdu 3709 Balanced Number(平衡数)--数位dp
Balanced Number Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) ...
-
HDU 3709 Balanced Number 求区间内的满足是否平衡的数量 (数位dp)
平衡数的定义是指,以某位作为支点,此位的左面(数字 * 距离)之和 与右边相等,距离是指某位到支点的距离; 题意:求区间内满足平衡数的数量 : 分析:很好这又是常见的数位dp , 不过不同的是我们这次 ...
-
HDU - 3709 - Balanced Number(数位DP)
链接: https://vjudge.net/problem/HDU-3709 题意: A balanced number is a non-negative integer that can be ...
-
hdu 5898 odd-even number 数位DP
传送门:hdu 5898 odd-even number 思路:数位DP,套着数位DP的模板搞一发就可以了不过要注意前导0的处理,dp[pos][pre][status][ze] pos:当前处理的位 ...
-
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 ...
-
HDU 5179 beautiful number 数位dp
题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5179 bc(中文): http://bestcoder.hdu.edu.cn/contes ...
-
HDU3709 Balanced Number —— 数位DP
题目链接:https://vjudge.net/problem/HDU-3709 Balanced Number Time Limit: 10000/5000 MS (Java/Others) ...
-
HDU 5898 odd-even number (数位DP) -2016 ICPC沈阳赛区网络赛
题目链接 题意:一个数字,它每个数位上的奇数都形成偶数长度的段,偶数位都形成奇数长度的段他就是好的.问[L , R]的好数个数. 题解:裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的 ...
随机推荐
-
I() 方法
I()方法的介绍及使用: http://www.jb51.net/article/51213.htm
-
Redis多机功能介绍
Redis多机功能目的:以单台Redis服务器过渡到多台Redis服务器 Redis单机在生产环境中存在的问题 1.内存容量不足 Redis使用内存来存书数据库中的数据,但是对于一台机器来说,硬件的内 ...
-
Spring Batch的事务– Part 3: 略过和重试
原文:https://blog.codecentric.de/en/2012/03/transactions-in-spring-batch-part-3-skip-and-retry/ This i ...
-
JS 动态显示 获取下拉框的多个值
<script type="text/javascript"> function GetProcessVal(i, t) { document.getElementsB ...
-
PHP魔术方法
魔术方法:两个下划线开头的格式. PHP中的魔术方法总结 :__construct, __destruct , __call, __callStatic,__get, __set, __isset, ...
-
dede从www跟目录迁移,网站空间
图集缩略图表名dede_uploads 字段url; 图集文章内部的图片表名dede_addonimages 字段imgurls 频道文章列表的图片 ...
-
eclipse启动报错
我的是win64位系统,eclipse,jdk1.8 64位 原因:网上说是jdk和eclipse的版本不一致导致的(32位jdk64位eclipse,或者相反): 解决过程: 安装了jdk1. ...
-
C++二维数组、指针、对象数组、对象指针
项目中用到,随手记一下: 1.二维数组.与指针 创建二维数组指针的方式: a.已知一维的大小 1 int **array=new int *[rows]; 2 (for int i=0;i<ro ...
-
【修改密码】Linux下修改Mysql的用户(root)的密码
修改的用户都以root为列.一.拥有原来的myql的root的密码: 方法一:在mysql系统外,使用mysqladmin# mysqladmin -u root -p password " ...
-
UMI开源项目
本文主要围绕UMI是什么及其特征.安装应用.模板例子等四个方面内容来讲解UMI,希望能够对初学者有所启发. 一. UMI是什么 UMI是可插拔的企业级反应应用程序框架. 二. 特征 特征