UVA529 Addition Chains (IDA*)

题目描述

传送门
这道题用了IDA*, (虽然我不太会)
(PS: 思路来源: 李煜东《算法竞赛进阶指南》CD附带代码)

可以发现一个很好的性质, 就是:

当前数列末尾数为a时, 凑成b至少需要$log_2(b/a)$log2​(b/a) 步. 因为用a凑b的话, 可以看成凑成$2^na = b$2na=b, 因为每次可以增大a的$2^n$2n(n为第几次), 所以n就是就是最小步数, 等于$log_2(b/a)$log2​(b/a) , 所以估价函数就可以利用这个性质

(1,2 无法算出正确值, 只好打表了)

上代码(本人比较喜欢重载, 码风有点丑, 敬请原谅):

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cmath>
# include <cstring>
# include <cstdlib>

using namespace std;

# define rep(i,j,k) for(int i=j;i<=k;i++)
# define per(i,j,k) for(int i=j;i>=k;i--)
# define clr(a) memset(a,0,sizeof(a))
# define vbg(a) memset(a,0x7f,sizeof(a))
# define sml(a) memset(a,0xff,sizeof(a))

const int MAX = 10010, INF = 0x3f3f3f3f;

int n, ans[MAX], lg2[MAX], maxdepth;

int log2 (int a) {
	int ans = 0, now = 1;
	for (; now < a; now *= 2, ans ++);
	return ans;
}

int Laststep (int depth) {
	if (ans[depth] > n)	return INF;
	return lg2[(int) ceil ( (double) n / ans[depth])];
}

void First () {
	int i;
	rep(i,1,MAX - 1) {
		lg2[i] = log2 (i);
	}
	return;
}

void Init () {
	cin>> n;
	if (n == 0)	exit (0);
	clr (ans);
	return;
}

bool IDA_star (int depth) {
	int i, j, last;
	per (i,depth - 1, 0) {
		if (ans[i] + ans[i] <= ans[depth - 1])	break;
		per(j,i,0) {
			if (ans[i] + ans[j] <= ans[depth - 1])	break;
			ans[depth] = ans[i] + ans[j];
			last = Laststep (depth);
			if (last == 0)	return 1;
			else if (last + depth < maxdepth) {
				if (IDA_star (depth + 1)) {
					return 1;
				}
			}
		}
	}
	return 0;
}

bool Solve () {
	if (n == 1) {
		cout<< "1"<< endl;
		return 1;
	}
	if (n == 2) {
		cout<< "1 2"<< endl;
		return 1;
	}
	ans[0] = 1;
	maxdepth = Laststep (0);
	for (; IDA_star (1) == 0;) maxdepth ++;
	int i;
	rep(i,0,maxdepth - 2) {
		cout<< ans[i]<< " ";
	}
	cout<< ans[maxdepth - 1]<< endl;
	return 0;
}
	
int main () {
	First ();
	for (; 1; ) {
		Init ();
		if (Solve ())	continue;
	}
	return 0;
}

评测记录: