B25 迭代加深 Addition Chains

#include <iostream>
using namespace std;

int n, d;     //d为搜索深度
int a[10005]; //存储加成序列

bool dfs(int u){ //搜索第u层
  if(u==d) return a[ u-1]==n;
  for(int i=u-1;i>=0;i--){//cut1:优化搜索顺序
    int t=a[ u-1]+a[i];
    if(t>n) continue;     //cut2:越界剪枝
    a[ u]=t;
    for(int j=u+1; j<=d; j++) t*=2;
    if(t<n) return False; //cut3:估价未来
    if(dfs(u+1)) return True;
  }
  return False;

B25 迭代加深 Addition Chains

#include <iostream>
using namespace std;

int n, d;     //d为搜索深度
int a[10005]; //存储加成序列

bool dfs(int u){ //搜索第u层
  if(u==d) return a[ u-1]==n;
  for(int i=u-1;i>=0;i--){//cut1:优化搜索顺序
    int t=a[ u-1]+a[i];
    if(t>n) continue;     //cut2:越界剪枝
    a[ u]=t;
    for(int j=u+1; j<=d; j++) t*=2;
    if(t<n) return False; //cut3:估价未来
    if(dfs(u+1)) return True;
  }
  return False;
}
int main(){
  a[0]=1;
  while(scanf("%d",&n),n){
    d=1;
    while(!dfs(1)) d++; //失败则增加一层
    for(int i=0; i<d; i++) printf("%d ",a[i]);
    puts("");
  }
}

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N], n,m;
bool v[N];
bool dfs(int x)
{
if(x==m) return a[m-1]==n;
memset(v,0,sizeof(v));
for(int i=x-1; i>=0; i--)
{
for(int j=i; j>=0; j--)
{
a[x]=a[i]+a[j];
if(a[x]<=n && a[x]>a[x-1])
{
if(!v[a[x]])//v[ a[x] ]的剪枝秒：当前a[1]--a[x-1]已经确定，a[x]的值只需尝试 一次
{
v[a[x]]=1;
if(dfs(x+1)) return 1;
}
}
}
}
return 0;
}
int main()
{
while(scanf("%d",&n)!=EOF && n)
{
a[0]=1;m=1;
while(!dfs(1)) m++;
for(int i=0; i<m; i++) printf("%d ",a[i]);
printf("\n");
}
return 0;
} 

#include<bits/stdc++.h>//请大家帮忙看看为什么这个会超时？
using namespace std;
    
const int N=110;
int a[N], n,m;
bool v[N];
    
bool dfs(int x)
{
    if(x>m) return a[m]==n;
    memset(v,0,sizeof(v));
    for(int i=x-1; i>=1; i--)
    {
        for(int j=i; j>=1; j--)
        {
            a[x]=a[i]+a[j];
            if(a[x]<=n && a[x]>a[x-1] && !v[a[x]])
            {
                v[a[x]]=1;
                if(dfs(x+1)) return 1;
            }
        }
    }
    return 0;
}
    
int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        a[1]=1;m=2;
        while(!dfs(2)) m++;
        for(int i=1; i<=m; i++) printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}