【题目描述】
An addition chain for n is an integer sequence with the following four properties:
a0 = 1
am = n
a0 < a1 < a2 < ... < am-1 < am
For each k (1<=k<=m) there exist two (not necessarily different) integers i and j (0<=i, j<=k-1) with ak=ai+aj
You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
【题目链接】
Addition Chains
【算法】
枚举构造答案,迭代加深搜索。
剪枝：
1、从大到小枚举i，j
2、排除冗余（判重）
【代码】
#include <stdio.h>
#include <cstring>
using namespace std;
int n,deep;
int ans[1000],v[1000];
bool dfs(int cur) {
if(cur>deep) {
if(ans[deep]==n) return 1;
return 0;
}
for(int i=cur-1;i>=0;i--) {
for(int j=i;j>=0;j--) {
if(ans[i]+ans[j]<=n&&!v[ans[i]+ans[j]]) {
ans[cur]=ans[i]+ans[j]; v[ans[i]+ans[j]]=1;
if(dfs(cur+1)) return 1;
v[ans[i]+ans[j]]=0;
}else if(ans[i]+ans[j]<=ans[cur-1]) break;
}
}
return 0;
}
int main() {
while(~scanf("%d",&n)&&n) {
printf("1"); ans[0]=1;
if(n==1) { puts(""); continue; }
for(deep=1;!dfs(1);deep++) memset(v,0,sizeof(v));
for(int i=1;i<=deep;i++) printf(" %d",ans[i]);
puts("");
}
return 0;
}