经典DFS PAT 1103

题意

给定正整数N、K、P,将N表示成K个整数，（可以相同，递减排列）的P次方的和，就是N=n1^P...nk^P。
如果有多种方案，那么选择底数和n1+n2...+nk最大的方案；
如果还有多种方案，那么选择底数序列的字典序最大的方案。

思路

步骤1：由于P不小于2，并且在单次运行中是固定的，因此不妨开一个vector<int> fac，在输入P之后就预处理出所有不超过N的n^p。为了方便下标与元素有直接的对应，这里应把0也存进去。
于是，对于N=10，P=2，fac[0]=0,fac[1]=1,fac[2]=4,fac[3]=9<10,结束

步骤2：接下来就是DFS函数，DFS函数用于从fac中选择若干个数，是的他们的和等于N，于是需要针对fac中的每个数，根据选与不选这个数来进入两个分支，因此DFS的参数中必须有：
1>.当前处理到的是fac的几号位，记为index;
2>.当前已经选择了几个数，记为nowk;
3>.由于目的是选出的数之和为N，因此参数中也需要记录当前选择出的数之和sum；
4>.为了保证有多个方案时底数之和最小，还需要在参数中记录当前选择出的数的底数之和facsum。
这样需要的参数就齐了。

void DFS(int index,int nowk,int sum,int facsum){}

此外，还需要开一个vector<int> ans,用来存放最优的底数序列，而用一个vector<int> temp来存放当前选中的底数组成的临时序列。


步骤3：考虑递归本身。注意：为了让结果能保证字典序大的序列优先被选中，需要让index从大到小递减来遍历，这样就总是能先选中fac中较大的数了。
显然，如果当前需要对fac[index]进行选择，那么就会有“选”与“不选”两种选择。如果不选，就可以把问题转化为对fac[index-1]进行选择，此时nowk、sum、facsum均不变，因此往DFS(index-1,nowk,sum,facsum)这条分支前进；如果选，由于每个数字可以重复选择，因此下一步还应当对fac[index]进行选择，但由于当前选择了fac[index]，需要把底数index加入当前序列temp中，同时让nowk+1、sum加上fac[index]、facsum加上index，就是往DFS(index,nowk+1,sum+fac[index],index+facsum)这条分支前进。显然，DFS必须在index不小于1时执行。

步骤4：那么，递归边界是什么呢？递归到什么时候停止呢？首先，如果到了某个时候sum==N 并且 nowk==k成立，
需要判断底数之和facsum是否比一个全局记录的最大底数之和maxfacsum更大，若是，就更新maxfacsum，并且把temp赋给ans。除此之外，当sum>N或者nowk>k时，不可能会产生答案，可以直接返回。

输入

169 5 2

输出

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>


using namespace std;


int n,k,p;

vector<int>  fac,temp,ans;

int max_fac_sum=-1;



int power(int x)
{
    int ans=1;

    for(int i=0;i<p;i++)
    {
        ans*=x;
    }

    return ans;


}


void init()
{
    int i=0,temp=0;

    while(temp<=n)
    {

        fac.push_back(temp);

        temp=power(++i);


    }




}


void DFS(int index,int nowk,int sum,int fac_sum)
{

    if( sum==n && nowk==k  )
    {
        if( fac_sum>max_fac_sum  )
        {
            max_fac_sum=fac_sum;

            ans=temp;

            return;

        }




    } 

    if( sum>n || nowk>k )
    {
        return ;
    }


    if(index-1>=0 )
    {

        temp.push_back(index);

        DFS(index,nowk+1,sum+fac[index],fac_sum+index); 



        temp.pop_back();

        DFS(index-1,nowk,sum,fac_sum);






    }









}




int main()
{

    scanf("%d%d%d",&n,&k,&p);

    init();

    DFS(fac.size()-1,0,0,0);

    if( max_fac_sum==-1 )
    {
        printf("Impossible\n");
    }
    else
    {
        printf("%d = %d^%d",n,ans[0],p);

        for(int i=1;i<ans.size();i++)
        {

            printf(" + %d^%d",ans[i],p);

        }









    }




    return 0;



}