要点

1. 三维状态表示，第一维记录数字，第二维记录已使用个数，第三维记录当前需要组成的数字，记录的量是各因子之和（应题意需求）
   • $f(i,j,k)$表示“只考虑前$i$各数字、已使用了$j$个数字且各数字$P$次幂之和恰好为$k$的选法集合”，属性：各因子之和$Max$
   • 有题解将三个维度抽象为“物品”、“体积”、“重量”，结合背包场景，比较好理解
2. 状态计算
   • 不选：$f(i,j,k) = f(i-1, j, k)$
   • 选：$f(i,j,k) = f(i-1,j-v,k-w)+value,(其中v=1,w=value^P)$，推导过程类似普通的完全背包，不过只多了一个维度
   • 综上：$f(i,j,k) = max(f(i-1,j,k),f(i-1,j-v,k-w)+value)$
3. 原题要求输出“各因子之和最大”、其次“因子序列字典序较大”的方案
   • 前者在状态表示中体现，$f(i,j,k)$所存数值即为当前各因子之和的最大值
   • 后者只需状态计算时升序枚举数字，逆推具体方案时，所得序列的字典序自然较大

代码

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int N, K, P;
    static int[][][] f = new int[25][410][410];

    public static void main(String[] args) {
        N = scanner.nextInt();
        K = scanner.nextInt();
        P = scanner.nextInt();
        // 枚举的数字n为 1~sqrt(N)   所求的数为N
        int n = (int) Math.sqrt(N), m = N;
        for (int i = 0; i < 25; i++) {  // 初始极小值
            for (int j = 0; j < 410; j++) {
                Arrays.fill(f[i][j], Integer.MIN_VALUE);
            }
        }
        f[0][0][0] = 0;  // 初始化边界条件 不使用任何数、已选0个且P次幂的和为0的选法 其因子之和为0
        for (int i = 1; i <= n; i++) {  // 枚举数字1~sqrt(N)
            int w = (int) Math.pow(i, P);  // 计算i的P次幂
            for (int j = 0; j <= K; j++) {  // 枚举已选个数
                for (int k = 0; k <= m; k++) {  // 枚举第三个维度 P次幂的和
                    f[i][j][k] = f[i - 1][j][k];  // 不选用数字i f(i,j,k) = f(i-1,j,k)
                    if (k >= w && j >= 1) {  // 如果当前数字可用
                        // f(i,j,k)=max(f(i,j,k),f(i,j-1,k-w)+i)  其中+i表示加上当前因子到旧状态的因子和里
                        f[i][j][k] = Math.max(f[i][j][k], f[i][j - 1][k - w] + i);
                    }
                }
            }
        }
        // 因子和不大于0 则无解
        if (f[n][K][m] <= 0) {
            System.out.println("Impossible");
            return;
        }
        // StringBuilder 动态生成字符串答案
        StringBuilder sb = new StringBuilder(String.format("%d = ", m));
        for (int i = n, j = K, k = m; i > 0 && j > 0 && k > 0; i--) {  // 从f(n,K,m)逆推
            int w = (int) Math.pow(i, P);  // 计算i（即当前使用数字）的P次幂
            // 如果可用且状态计算时已用 则更新答案  对于01背包逆推只需一次if 对于完全背包需一次循环
            while (k >= w && f[i][j][k] == f[i][j - 1][k - w] + i) {
                sb.append(String.format("%d^%d + ", i, P));  // 更新答案、j、k状态
                k -= w;
                j--;
            }
        }
        sb.delete(sb.length() - 3, sb.length());  // 去除末尾“ + ”三个多余字符
        System.out.println(sb);
    }
}