Addition Chains

For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.
Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.

C++(g++ 7.5.0) 解法, 执行用时: 18ms, 内存消耗: 316K, 提交时间: 2022-10-29 16:23:41

//Author:XuHt
#include <cstring>
#include <iostream>
using namespace std;
const int N = 106;
int n, ans[N], dep;

bool dfs(int now) {
	if (now == dep) return ans[now] == n;
	bool v[N];
	memset(v, 0, sizeof(v));
	for (int i = now; i; i--)
		for (int j = i; j; j--) {
			int num = ans[i] + ans[j];
			if (num <= n && num > ans[now] && !v[num]) {
				ans[now+1] = num;
				if (dfs(now + 1)) return 1;
				else v[num] = 1;
			}
		}
	return 0;
}

int main() {
	ans[1] = 1;
	while (cin >> n && n) {
		dep = 1;
		while (!dfs(1)) ++dep;
		for (int i = 1; i <= dep; i++) cout << ans[i] << " ";
		cout << endl;
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 296K, 提交时间: 2022-04-20 22:35:32

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,dm,d[N];
bool vis[N],fl;
inline void dfs(int x,int lst){
	if(x>dm){
		if(d[dm]==n)fl=true;
		return;
	}
	for(int i=lst;i<x;i++){
		for(int j=1;j<=i;j++){
			d[x]=d[i]+d[j];
			dfs(x+1,i+1);
			if(fl)return;
			d[x]=0;
		}
	}
}
int main(){
	while(~scanf("%d",&n)){
		if(n==0) break;
		dm=1;
		memset(vis,0,sizeof(vis));
		fl=false;
		d[1]=1;
		for(;!fl;dm++)dfs(2,1);
		for(int i=1;i<dm;i++) printf("%d ",d[i]);
		puts("");
	}
	return 0;
}

详情