AcWing 170. 加成序列
原题链接
简单
作者:
ZTEG
,
2019-11-10 20:12:51
,
所有人可见
,
阅读 1397
#include<bits/stdc++.h>
using namespace std;
int f[105];
int a[105];
int tot;
int n,all;
bool dfs(int MAX) {
if(tot>all)
return 0;
if(MAX==n) {
for(int i=1; i<=n; i++)
if(f[i])
cout<<i<<" ";
cout<<endl;
return 1;
}
bool dhy[105];
memset(dhy,0,sizeof(dhy));
for(int i=tot; i>=1; i--)
for(int j=tot; j>=i; j--) {
if(!dhy[a[i]+a[j]]&&!f[a[i]+a[j]]&&a[i]+a[j]>MAX&&a[i]+a[j]<=n) {
dhy[a[i]+a[j]]=1;
f[a[i]+a[j]]=1;
tot++;
a[tot]=a[i]+a[j];
if(dfs(a[i]+a[j]))
return 1;
tot--;
f[a[i]+a[j]]=0;
}
}
return 0;
}
int main() {
while(1)
{
memset(f,0,sizeof(f));
cin>>n;
if(!n)
break;
tot=1;
a[1]=1;
f[1]=1;
all=1;
for(all;;all++)
if(dfs(1))
break;
}
return 0;
}