【PAT甲级 - C++题解】1103 Integer Factorization

1103 Integer Factorization

The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.

Input Specification:

Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.

Output Specification:

For each case, if the solution exists, output in the format:

N = n[1]^P + ... n[K]^P

where n[i] (i = 1, …, K) is the i-th factor. All the factors must be printed in non-increasing order.

Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122+42+22+22+12, or 112+62+22+22+22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen – sequence { a1,a2,⋯,aK } is said to be larger than { b1,b2,⋯,bK } if there exists 1≤L≤K such that ai=bi for i<L and aL>bL.

If there is no solution, simple output Impossible.

Sample Input 1:

169 5 2

Sample Output 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

题意

正整数 N 的 K−P 分解，是将 N 写为 K 个正整数的 P 次幂的和。

请你编写一个程序，给定 N,K,P 的情况下，找到 N 的 K−P 分解。

思路

状态表示： f[i][j][k] 表示所有只考虑前 i 个物品，且总 p 次方和恰好是 j ，且数的个数恰好是 k 的所有选法的集合。

这个集合意思是存的答案中用到的所有数的总和，比如 n = 169, k = 5, p = 2 的最佳拆分答案为 6^2 + 6^2 + 6^2 + 6^2 + 5^2 ，所以集合 f[5][169][5] = 6 + 6 + 6 + 6 + 5 = 29 。

故我们需要先求出最佳的集合数，然后再反过来拆分集合得到最终的答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 410;
int n, k, p;
int f[21][N][N];
//计算a的b次方
int power(int a, int b)
{
    int res = 1;
    for (int i = 0; i < b; i++)    res *= a;
    return res;
}
int main()
{
    cin >> n >> k >> p;
    //初始化
    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0;
    //开始dp
    int m;
    for (m = 1;; m++)   //从1开始向后枚举
    {
        int v = power(m, p);   //计算m的p次方
        if (v > n) break;  //如果当前枚举的数已经超过n，则dp结束
        //更新数据
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= k; j++)
            {
                //不选当前数
                f[m][i][j] = f[m - 1][i][j];
                //选当前数
                if (i >= v && j) f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);
            }
    }
    m--;
    //从得到的集合中开始拆分出答案
    if (f[m][n][k] < 0)    puts("Impossible");
    else
    {
        printf("%d = ", n);
        bool is_first = true;
        while (m)
        {
            int v = power(m, p);
            //判断答案集合中是否有m
            while (n >= v && k && f[m][n - v][k - 1] + m == f[m][n][k])
            {
                if (is_first)    is_first = false;
                else    printf(" + ");
                printf("%d^%d", m, p);
                n -= v, k--;
            }
            m--;
        }
    }
    return 0;
}