AC Code1

#include<iostream>
#include<cmath>
using namespace std;
int N, k, p;
const int K = 405;
int n[K], res[K], v[K];
int ans = -1, cnt = 0;
int len;

/*
 x: 代表当前累计
 i: 代表当前次数
 j: 代表当前 v[i] 数组所在位置

如果不是从 v[i] 里面选数，而是直接从 1-N 循环的话，会超时
通过提前将 小于N的所有 p 次幂全部求出，存放于数组之中，大大减少比较次数
*/

void dfs(int x, int i, int j) {
    // 正确结束
    if (x == N && i == k) {
        cnt = 0;
        for (int t = 0; t < k; t++) cnt += res[t];
        if (ans < cnt) {
            ans = cnt;
            for (int m = 0; m < k; m++) n[m] = res[m];
        }
        return;
    }

    // 其他递归
    for (int t = j; t > 0; t--) {
        if (i + 1 <= k && x + v[t] <= N) {  // 剪枝，选择合适的比较条件
            res[i] = t;
            dfs(x + v[t], i + 1, t);
        }
    }
}

int main() {

    cin >> N >> k >> p;
    int j = 0;
    while (pow(++j, p) <= N) {
        v[j] = pow(j, p);
    }

    dfs(0, 0, j-1);

    if (ans == -1) cout << "Impossible";
    else {
        printf("%d = %d^%d", N, n[0], p);
        for (int i = 1; i < k; i++) {
            printf(" + %d^%d", n[i], p);
        }
        cout << endl;
    }

    return 0;
}