思路

本題是深搜的一個應(yīng)用：排列組合，選取給定的序列中的部分?jǐn)?shù)字（可重復(fù)選擇）使得滿足給定條件。放到本題中：給定序列，從1到x（x是第一個p次大于等于n的數(shù)），滿足條件：每項的p次和為n.

組合按照非增序排列，若有多組，選擇和最大的一組結(jié)果。若結(jié)果仍不唯一，選擇兩組數(shù)字中，第一個不相等元素中較大的那個組合。例如9 9 7 6；9 9 7 3；，第一個不相等的元素為6和3 選擇6 的元素的那個組合。

同時，考慮到pow運算多次重復(fù)，可以使用打表的技巧，以減少用時，通過樣例5。

樣例四的數(shù)據(jù)應(yīng)該類似 23 1 1.

和力扣39 40 一樣，建議沒思路的同學(xué)可以先做力扣

代碼

#include <bits/stdc++.h>
using namespace std;

int n, k, p;
const int maxn = 403;
int power[maxn];
vector<int> nums, num2;
vector<int> ans;
int maxsum = 0;

void dfs(int len, int target, int idx, int numsum, vector<int>& combine) {
    if (idx >= nums.size()) return;
    if (len == 0 && target == 0) {
        if (numsum >= maxsum) {
            ans = combine;
            maxsum = numsum;
        } 
        return;
    } else if(len == 0 || target == 0) {
        return;
    }
    dfs(len, target, idx + 1, numsum, combine); //no
    if (power[nums[idx]] <= target) {
        combine.push_back(nums[idx]);
        target -= power[nums[idx]];
        len -= 1;
        numsum += nums[idx];
        dfs(len, target, idx, numsum, combine);
        numsum -= nums[idx];
        len += 1;
        target += power[nums[idx]];
        combine.pop_back();
    }
    
}

int main() {
    cin>>n>>k>>p;
    for (int i = 1; i <= n; i++) {
        power[i] = pow(i, p);
        if (power[i] > n) break;
        num2.push_back(i);
    }
    for (int i = num2.size() - 1; i >= 0; i--) {
        nums.push_back(num2[i]);
    }
    vector<int> combine;
    dfs(k, n, 0, 0, combine);
    if (ans.size() == 0) {
        cout<<"Impossible"<<endl;
        return 0;
    }
    cout<<n<<" =";
    for (int i = 0; i < k; i++) {
        printf(" %d^%d", ans[i], p);
        if (i != k - 1) printf(" +");
    }
     
}