A30295. 整数分解
题目描述
整数分解
题目描述
正整数 N 的 K-P 分解是指将 N 写成 K 个正整数的 P 次方的和。本题就请你对任意给定的正整数 N、 K、 P，写出 N 的 K-P 分解。
时间限制： 8000 内存限制： 262144
输入
输入在一行给出 3 个正整数 N (≤ 400)、 K (≤ N)、 P (1 < P ≤ 7)，以空格分隔。
输出
如果存在解，则按下列格式输出： N = n[1 ]^P + ... n[K]^P 其中 n[i] (i = 1 , ..., K) 是第 i 个分解因子。所有的分解因子要按非增顺序输出。注意： 解可能是不唯一的。例如 169 的 5-2 分解就存在 9 个解，如 12^2 + 4^2 + 2^2 + 2^2 + 1 ^2 或 11 ^2 + 6^2 + 2^2 + 2^2 + 2^2 等等。你必须输出分解因子和最大的那个解。如果还不唯一，则输出具有最大的分解因子序列的解 —— 我们称序列 { a1 , a2 , … , aK} 比序列 { b1 , b2 , … , bK } 大，如果存在 1 ≤ L ≤ K 使得 ai =bi 对于 i < L 成立，并且有 aiL > bL 。如果解不存在，则输出`Impossible`。
样例输入
样例#1：
169 5 2
样例#2：
169 167 3
样例输出
样例#1：
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
样例#2：
Impossible
参考答案
#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;
}答案解析
题意
正整数 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 。
故我们需要先求出最佳的集合数，然后再反过来拆分集合得到最终的答案。