题解 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; } ```