#include <bits/stdc++.h>

using namespace std;

const int N = 22, M = 410;

int f[N][M][M];
int n, k, p, t;
int v[N], w[N], value[N];

int main()
{
    scanf("%d%d%d", &n, &k, &p);

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0;

    for (int i = 1; i <= N; i ++ )
    {
        if (pow(i, p) >= n) break;
        v[i] = pow(i, p);
        w[i] = 1;
        value[i] = i;
        t ++ ;
    }

    for (int i = 1; i <= t; i ++ )
        for (int j = 0; j <= n; j ++ )
            for (int h = 0; h <= k; h ++ )
            {
                f[i][j][h] = f[i - 1][j][h];
                if (j - v[i] >= 0 && h - w[i] >= 0) f[i][j][h] = max(f[i][j][h], f[i][j - v[i]][h - w[i]] + value[i]);
            }


    if (f[t][n][k] < 0) puts("Impossible");
    else
    {
        bool is_PAT = true;
        while (t && n && k)
        {
            if (f[t][n][k] == f[t][n - v[t]][k - w[t]] + value[t])
            {
                if (is_PAT)
                {
                    is_PAT = false;
                    printf("%d = %d^%d", n, t, p);
                }
                else
                {
                    printf(" + %d^%d", t, p);
                }

                n -= v[t], k -= w[t];
            }
            else t -- ;
        }
    }

    return 0;
}

DFS + 剪枝

#include <bits/stdc++.h>

using namespace std;

const int N = 21, M = 410;

int n, k, p;
int v[N];
int resume = -1;

vector<int> tes, ans;

void dfs(int t, int n, int cnt, int sum)
{
    if (cnt == k && n == 0)
    {
        if (sum > resume)
        {
            resume = sum;
            ans = tes;
        }
        return;
    }

    while (t)
    {
        if (n - v[t] >= 0 && cnt + 1 <= k)
        {
            tes[cnt] = t;
            dfs(t, n - v[t], cnt + 1, sum + t);
        }
        t -- ;
    }
}
int main()
{
    scanf("%d%d%d", &n, &k, &p);

    tes.resize(k);

    int t = 0;
    for (int i = 1; i <= 20; i ++ )
    {
        if (pow(i, p) > n) break;
        v[i] = pow(i, p);
        t ++ ;
    }

    dfs(t, n, 0, 0);

    if (resume == -1) puts("Impossible");
    else
    {
        bool is_first = true;
        for (int i = 0; i < ans.size(); i ++ )
        {
            if (is_first)
            {
                 cout  << n << " = " << ans[i] << '^' << p;
                 is_first = false;
            }
            else
            {
                cout << " + " << ans[i] << '^' << p;
            }
        }
    }

    return 0;
}