[Vijos1308]埃及分数(迭代加深搜索 + 剪枝)
2024-10-19 22:33:06
迭代加深搜索是必须的,先枚举加数个数
然后搜索分母
这里有一个强大的剪枝,就是确定分母的范围
#include <cstdio>
#include <cstring>
#define N 100001
#define LL long long
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y)) int n, flag, best = 9999999;
int ans[N], s[N] = {1}; inline void dfs(LL a, LL b, int k)
{
LL i, x, y, l, r;
if(!a)
{
flag = 1;
best = s[n];
for(i = 1; i <= n; i++)
ans[i] = s[i];
return;
}
if(k > n) return;
l = max(s[k - 1] + 1, b / a);
r = min(best - 1, b * (n - k + 1) / a);
for(i = l; i <= r; i++)
if(a * i >= b)
{
x = a * i - b;
y = b * i;
s[k] = i;
dfs(x, y, k + 1);
}
} int main()
{
int i;
LL a, b;
scanf("%lld %lld", &a, &b);
while(!flag)
{
n++;
dfs(a, b, 1);
}
for(i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}
最新文章
- 通过docker-machine和etcd部署docker swarm集群
- 解决clone问题之外的体会
- xmpp4-总览
- Day04_JAVA语言基础第四天
- for each 循环
- RMAN-FORMAT-CONFIGURE及动态性能表
- 高频(工作频率为13.56MHz)
- Poj 2299 Ultra-QuickSort(归并排序)
- GridView点击空白地方事件扩展
- ZYNQ-7000 Unable to connect to ps7_cortexa9 解决方案
- this与super使用总结(java)
- 【开源分享】2018CRM C# 源码(基于小黄豆CRMv2.0.925.3版本功能更新)
- JAVA多线程-实现通讯
- windows 8.1 cmd命名提示符全屏
- 使用Shader制作loading旋转动画
- Learning Structured Representation for Text Classification via Reinforcement Learning 学习笔记
- css3 媒体查询常用适配
- SE Springer小组之《Spring音乐播放器》需求分析说明书一
- mysql windows开启客户端连接权限
- Android 获取内存信息
热门文章
- FPGA的嵌入式RAM
- 【Web应用-网络连接】Azure Web 应用对外连接数上限分析
- 学习python报错处理
- Openjudge 1.13-23:区间内的真素数
- tomcat配置 —— 各个目录的作用
- dataSource&#39; defined in class path resource [org/springframework/boot/autocon
- 兼容IE6\7\8浏览器的html5标签的几个方案
- gEdit - GTK+ 基础文本编辑器
- winhex与磁盘格式与 数据恢复
- 歌乐第二弹:C++九九八十一