题目跳转
Luogu P1763
题目大意
把一个分数，分解为若干个分子为一且分母不同的的和。
最终输出，以分解的个数最小为前提，最小的一个分数的分母最小，即该分数最大。
思路
IDDFS - 剪枝
暴力写的话，IDDFS比较模板，难点在于剪枝。(我认为这个剪枝事实上让这道题有点IDA*的意味了)
题目中说明答案中的分母最大为1e7，然而直接循环是不能接受的。
因此，我们要缩小遍历范围。
下界 —— max(取的上一个数 1,当前相减后剩余的分数的存在的最大的1/x) 上界 —— min(1e7, 剩余的层数都取同一个分母(使得总和与当前的剩余相等)
CODE
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010;
struct Node
{
int up, down;
} a;
int path[N], ans_path[N];
bool flag;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
Node Node_sub(Node a, Node b) // a-b
{
LL tx, ty, d;
ty = (LL)a.down * b.down;
tx = (LL)a.up * b.down - (LL)b.up * a.down;
if (!tx)
return (Node){0, 1};
d = gcd(tx, ty);
if (d)
tx /= d, ty /= d;
if (!d || ty > (int)1e7 || tx < 0)
tx = -1;
if (tx == 0)
ty = 1;
return (Node){(int)tx, (int)ty};
}
void dfs(int u, int id, Node remain, int depth)
{
if (u == depth && remain.up == 0)
{
if (!flag || path[u - 1] < ans_path[u - 1])
{
memcpy(ans_path, path, sizeof path);
flag = true;
}
return;
}
int l = max(id, remain.down / remain.up), r = min(remain.down * (depth - u) / remain.up, (int)1e7); // 强力剪枝 - 缩小范围
for (int i = l; i <= r; i )
{
Node t = Node_sub(remain, (Node){1, i});
if (t.up == -1)
continue;
path[u] = i;
dfs(u 1, i 1, t, depth);
path[u] = 0;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
cin >> a.up >> a.down;
int depth = 1;
while (true)
{
dfs(0, 2, a, depth);
if (flag)
break;
depth ;
}
for (int i = 0; i < depth; i )
cout << ans_path[i] << ' ';
cout << 'n';
return 0;
}
