题解 UVA529 【Addition Chains】
lx_zjk
·
·
题解
UVA529 【Addition Chains】
好像是垃圾一本通里的题目，前置知识:迭代加深搜索 不懂的可以看我博客
内附迭代加深的模板
首先 先看题目 发现是 UVA的题目，立刻反应到，输出要有格式，这也是我交了那么多次没A的理由
然后 看数据范围 1 to 10000 ，然后仔细观察这个数列 易发现这个数列不简单必须符合一个规律，就是f[n] \leq 2 * f[n-1],至于证明，可以发现等比数列1 2 4 ... 2^n的和为2*2^n-1,那么如果要不重不漏的组合出所有数，则下一位为2 * 2 ^n 这样即可以作为一个剪枝
还有几个剪枝写在code里，如果不懂可以私我
# code
```
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
inline ll read() {
ll f = 1, x = 0;char ch;
do {ch = getchar();if (ch == '-')f = -1;} while (ch > '9' || ch < '0');
do {x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
return f * x;
}
const int MAX_N = 1e4 + 5;
int n, a[MAX_N], maxdepth;
bool dfs (int depth,int maxdepth)
{
if (a[depth - 1] > n) return false;
if (depth == maxdepth ) return a[depth - 1] == n;
//前面提到的剪枝
if (a[depth-1]*((ll)1<<(maxdepth - depth))<n)return false;
bool st[MAX_N] = {0};
//枚举顺序 从大到小 这样使搜索树上端的分叉减小
for(int i = depth - 1; i >= 0; i -- )
{
for(int j = i; j >= 0; j -- )
{
int s = a[i] + a[j];
//保证序列严格递增 且不大于n 而且保证其未被搜索到过 减掉冗余信息
if (s > n || s <= a[depth - 1] || st[s]) continue;
a[depth] = s;
st[s] = true;
if (dfs (depth + 1, maxdepth)) return true;
}
}
return false;
}
int main ()
{
a[0] = 1;
while (cin >> n, n)
{
maxdepth = 1;
while (!dfs(1, maxdepth)) maxdepth ++ ;
cout<<a[0];
for (int i = 1; i < maxdepth; i ++ ) cout<<" "<<a[i];
cout << endl;
}
return 0;
}
```