由于考试将近，时间愈发珍贵，复习和学习的步调同比加快。但是，还行，还能喘过气来主要还是因为做题少才显得不是那么忙
今天认真学习了深搜DFS和广搜BFS。看了大量的代码，进行拙劣思考并结合一个深搜的题目浅谈自己的收货体会。
深搜和广搜的思想我不说了，我讲只能是班门弄斧。不如说点实在的
不哆嗦，把题目押上来~

The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.

Input Specification:
Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.

Output Specification:
For each case, if the solution exists, output in the format:
N = n[1]^P + ... n[K]^P

题目没有粘全省的题目占了一大片文章显得我在水字原题直达车
老规矩，我来解释

意思不难，
先给你一个目标数字N，
然后再给你“个数”K，
让你求出K个某某数字的P次方，
让这K个数的和等于N
木了~

这里有一个关键我们必须要想到
你想，给了你目标数字N，你的组合成员A，起码A^p 要小于N 叭。
当(A+1)^p>N时候，诶~~这不就来了吗？大喊一声哪里跑
立即推--->你的遍历范围在0~A里面，至于如何遍历，这里选取深度优先搜索

我们预先准备好
1.算次方的函数power。这没啥好说的
2.init初始化函数，不用啥参数，功能，是把你算出来的某某数的次方，推到vector里面，并且是把所有能推进去的全推进去。（当然要和power搭配使用）
3.注意偶，我们搜索的时候，是从最大个那个数A（就是A^p恰好不超过N）向前搜索。向前，向前，前.....
4.当有多个序列时候，输出字典序最大的，这个简单，但我还是说一下

这道题目的思维量，相比之前我更过得，要复杂许多，但不是不可理解，只是暂时难以掌握。需要时间的打磨。

代码如下

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int targetSum;//给出的目标数字N
int totalNum;//这是那个所谓的K
int exponent;//这是指数P
int maxFacSum = -1;

vector<int> fac;//这个放进那些某某数的P次方
vector<int> ans;//存放字典序最大的序列，也就是答案
vector<int> temp;//临时存放，递归时候用得着

int power(int x)//这个函数没什么说的，一看就懂
{

    int ans = 1;
    for(int i = 0 ; i< exponent ; i++)
    {
        ans *= x;
    }
    return ans;
}

void init()//这个是初始化函数。我认为这是为了main函数简洁起见，封装成了函数
{
    int i = 0 ; 
    int temp = 0;
    while (temp <=targetSum)
    {
        fac.push_back(temp);
        temp = power(++i);
    }
}

void DFS(int index , int nowK , int sum ,int facsum)//core thought
{


    if(sum == targetSum && nowK == totalNum)
    {
        if(facsum > maxFacSum)
        {
            ans = temp;
            maxFacSum = facsum;
        }
        return;
    }
/*
是否可以结束的判断，一定放在DFS内部的前面，
这里的条件满足是“当你算到的和，等于了目标，并且够了个数K”，就能更新最佳答案并且返回了
*/



/*
要是算的比目标的大，并且超出了要求个数K，就没有继续下去的必要了，直接返回
*/
    if(sum > targetSum || nowK > totalNum)
    {
        return;
    }


//这里应该算是核心的核心
    if(index -1 >= 0)
/*index是我们之前说的那个  “某某数”  ，因为是向前遍历，所以index后面是大于等于0
至于为什么是index要非得减掉1，这是因为我们的fac第一个数字是0,0的多少次方还是0（0^0除外），所以没有选择第一个数字的必要
  */
  {
        temp.push_back(index);//如果我们选择这个index的话
        DFS(index, nowK +1 , sum + fac[index] , facsum + index);//就这么操作，
//解释一下四个参数，index表示我从index这里继续往下遍历；nowK+1说明我现在又离凑齐K个近了一步；
sum+fac[index]说明我离凑齐N又近了一步；facsum+index记录着我这K个数字的组成成员的和，方便以后比较字典序
        temp.pop_back();//记得需要pop掉才能继续寻找
        DFS(index-1, nowK  , sum  , facsum );//我们不选这个index，就是这个操作，参数和上面相同的道理
    }



}

int main()
{
    scanf("%d%d%d",&targetSum,&totalNum,&exponent);
    init();
    DFS(fac.size() -1 , 0 , 0 ,0);//从后面往前遍历，开始的时候个数啊，总和啊，底数总和啊，都暂且为0
    if(maxFacSum == -1 ) printf("Impossible\n");//这就是没找到，说不可楞就行
    else
    {
        printf("%d = %d^%d",targetSum,ans[0],exponent);//输出分成两部分，先输出等于...
        for(int i = 1 ; i < ans.size() ; i++)
        {
            printf(" + %d^%d",ans[i],exponent);//后面就是加几加几了，后面的规律一样了，循环就行
        }
    }
    return 0;
}

我觉得我把代码解释的够详细了，简直是保姆级别手把手/手动滑稽

ok，课代表自动滚上来~

深搜的模型

void DFS(参数)
{    
1.  判断边界，这可能会有若干段代码，因题而异了
  
2.  核心的核心，对每一种进行遍历
for（int i= 0 ; i < n ;i ++）
{
巴拉巴拉
DFS(递归，这是灵魂)
回退，这个不要忘，很重要
}
return ；
}

我最近在思考为了把文章写得更加生动，总想插入一些图片把文章生动化，但是苦于没有素材，只能一点一点积累。从下一篇文章开始吧，多放几张有趣的图片。

开始吟唱~~
晚安

886~~~