题解 P7071 【优秀的拆分（暂无数据）】
Chinshyo
2020-11-07 21:41:17
# 我的思路
这道题读完后有一种想做$ dp $的冲动，但是先冷静，有没有发现其实$ dfs $ 比$ dp $更胜一筹。我们可以定义一个变量叫$ last $从最初始的2开始，不管是取还是不取，都每次乘上2。最后输出是用一个类似于哈希表的数组保存取了那些数。
# 递归过程
一共带上3个变量，$ dep $，$ sum $和$ last $。每次递归$ dep+1,last*=2 $。然而$ sum $只有满足条件的情况下增加总和。递归代码如下：
```cpp
void dfs(int dep,int sum,int last)
{
if(flag) return;
if(dep>7)//7其实是题目里数据样例最大次幂
{
if(sum==n) {
flag=true;
for(int i=1;i<=7;i++)
{
p[i]=h[i];//更新哈希表
}
}
}
else
{
dfs(dep+1,sum,last*2);
if(sum+last<=n)
{
h[dep]=1;
dfs(dep+1,sum+last,last*2);
h[dep]=0;
}
}
}
```
# 结果输出
用完哈希表就很好输出了，直接一个个枚举那个在选中的元素中那个就可以输出。代码如下:
```cpp
for(int i=7;i>=1;i--)
{
if(p[i]==1)//判断最终的哈希表
{
cout<<m(2,i-1)<<" ";
k=1;
}
}
```
# $ Code $
```cpp
#include<bits/stdc++.h>
using namespace std;
int m(int a,int b)
{
if(b==0) return a;
else a=a*m(a,b-1);
}
int n;
int h[11],p[11];
bool flag=false;
void dfs(int dep,int sum,int last)
{
if(flag) return;
if(dep>7)//7其实是题目里数据样例最大次幂
{
if(sum==n) {
flag=true;
for(int i=1;i<=7;i++)
{
p[i]=h[i];//更新哈希表
}
}
}
else
{
dfs(dep+1,sum,last*2);
if(sum+last<=n)
{
h[dep]=1;
dfs(dep+1,sum+last,last*2);
h[dep]=0;
}
}
}
int main()
{
//freopen("power.in","r",stdin);
//freopen("power.out","w",stdout);
cin>>n;
memset(h,0,sizeof(h));
memset(p,0,sizeof(p));
dfs(1,0,2);
int k=0;
for(int i=7;i>=1;i--)
{
if(p[i]==1)
{
cout<<m(2,i-1)<<" ";
k=1;
}
}
if(k==0) cout<<-1<<endl;
return 0;
}
```