生命不息,奋斗不止

题解 P7071 【优秀的拆分(暂无数据)】

2020-11-07 21:41:17


我的思路

这道题读完后有一种想做$ dp $的冲动,但是先冷静,有没有发现其实$ dfs $ 比$ dp $更胜一筹。我们可以定义一个变量叫$ last $从最初始的2开始,不管是取还是不取,都每次乘上2。最后输出是用一个类似于哈希表的数组保存取了那些数。

递归过程

一共带上3个变量,$ dep $,$ sum $和$ last $。每次递归$ dep+1,last*=2 $。然而$ sum $只有满足条件的情况下增加总和。递归代码如下:

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;
        }
    }
}

结果输出

用完哈希表就很好输出了,直接一个个枚举那个在选中的元素中那个就可以输出。代码如下:

for(int i=7;i>=1;i--)
{
  if(p[i]==1)//判断最终的哈希表
  {
    cout<<m(2,i-1)<<" ";
    k=1;
  }
}

$ Code $

#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;
}