搜索法 | 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=;

int dpow(int a,int n){

    int ans=;

    while(n--){

        ans*=a;

    }

    return ans;

}

void init(){

    while(){

        proc[sz]=dpow(sz,p);

        if(proc[sz]>) break;

        sz++;

    }

}

vector<int> ans;

vector<int> path;

int best_num_sum=-;

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+,sum+proc[num],num_sum+num);

    path.pop_back();

    //don't choose, continue

    if(num>){

        dfs(num-,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,,,);

    if(ans.size()){

        O("%d =",n);

        FF(i,ans.size()){

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

            if(i!=ans.size()-)

                O(" +");

        }

    }else{

        puts("Impossible");

    }

    return ;

}

巴特西

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

最新文章

热门文章