搜索法 | 1103 dfs搜索：符合条件的多项式

其实这题我已经写过两遍了，但都是在看过算法笔记的情况下写的。方法不难，只要能想出来。

找到一个项数为k，每项为p次幂，和为n，并且在有多个结果的情况下要求数字之和最大的一个多项式。如果数字之和相等。还要要求下标最大。

因为曾经看过答案，很多处理方法都有印象。这题的思维的确巧妙，如果能好好理解，就能掌握隐式图dfs搜索的内核。

对于每个dfs递归搜索函数，有两个后继：①选择这个数。 ②不选这个数。

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>


#define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 1010
#define MAX 0x06FFFFFF
#define V vector<int>

using namespace std;

int n,k,p; 
int proc[LEN];
int sz=0;

int dpow(int a,int n){
    int ans=1;
    while(n--){
        ans*=a;
    }
    return ans;
}

void init(){
    while(1){
        proc[sz]=dpow(sz,p);
        if(proc[sz]>400) break;
        sz++;
    }
}

vector<int> ans;
vector<int> path;
int best_num_sum=-1;

void dfs(int num,int len,int sum,int num_sum){
    if(sum>n || len>k) return;
    if(sum==n && len==k){
        if(num_sum>best_num_sum){
            best_num_sum=num_sum;
            ans=path;
        }
        return;
    }
    //choose
    path.push_back(num);
    dfs(num,len+1,sum+proc[num],num_sum+num);
    path.pop_back();
    //don't choose, continue
    if(num>1){
        dfs(num-1,len,sum,num_sum);
    }
}

int main(){
//    freopen("I:\pat\图的遍历\1103.txt","r",stdin);
    int a,b,i,j;
    I("%d%d%d",&n,&k,&p);
    init();
    dfs(sz,0,0,0);
    if(ans.size()){
        O("%d =",n);
        FF(i,ans.size()){
            O(" %d^%d",ans[i],p);
            if(i!=ans.size()-1)
                O(" +");
        }
    }else{
        puts("Impossible");
    }
    return 0;
}