个人练习-PAT甲级-1103 Integer Factorization

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224

题目大意：给出三个整数N,K,P，要求将N分解成K个整数的P次方之和。如果分解不唯一，取这K个数之和最大的序列；如果还不唯一，则取大的序列（从大到小排序，a[i]=b[i]但a[i+1]>b[i+1]，则a[]更大）

这种题型碰到的不多，开始根本没思路，想着暴力枚举那肯定超时。看了柳神代码后惊为天人，这么短的代码就OK了。看了一遍思路应该就是DFS+剪枝。

首先，确定这K个底数的范围，最大的就是N开P次方，讲所有可能的底数的P次方存进一个数组base[]里，方便之后使用。

    int num = 0;while (pow(num, P) <= N) {
    base.push_back(pow(num, P));num++;}

之后用一个长度为K的vectortmp_ans来存当前的答案，pos表示到第几位为止是有效的（即当前填到第几位了）。

开始时我想的是不用固定长度的vector，直接push_back()再pop_back()，这样就不用传pos了，但看了柳神答案后才发现这样子太蠢了，反正正确答案只有一个，错误的总会被覆盖掉，推进推出太麻烦了。

而且如果无解，也不需要用到序列来判断，而是根据max_base_ans即所有基底的和是否是-1来判断就好了。因为如果有了一个合法的序列，max_base_ans肯定就大于0了，这个合法的序列也会被存到ans中。

另外，扫描是从大到小扫描的，解决了取更大序列的要求。

	while (idx > 0) {
    if (tmp_sum + base[idx] <= N) {
    tmp_ans[pos] = idx;DFS(idx, tmp_sum + base[idx], base_sum + idx, pos + 1);}if (idx == 1)return;idx--;}

剪枝：如果已经有K个数了，除非次方和等于N切基底和更大，否则不要。

    if (pos == K) {
    if (tmp_sum == N && base_sum > max_base_sum) {
    ans = tmp_ans;max_base_sum = base_sum;}return;}

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>using namespace std;int N, K, P;
int max_base_sum, pos;
vector<int> base;
vector<int> ans, tmp_ans;void DFS(int idx, int tmp_sum, int base_sum, int pos) {
    if (pos == K) {
    if (tmp_sum == N && base_sum > max_base_sum) {
    ans = tmp_ans;max_base_sum = base_sum;}return;}while (idx > 0) {
    if (tmp_sum + base[idx] <= N) {
    tmp_ans[pos] = idx;DFS(idx, tmp_sum + base[idx], base_sum + idx, pos + 1);}if (idx == 1)return;idx--;}
}int main() {
    max_base_sum = -1;pos = 0;scanf("%d %d %d", &N, &K, &P);int num = 0;while (pow(num, P) <= N) {
    base.push_back(pow(num, P));num++;}tmp_ans.resize(K);DFS(base.size()-1, 0, 0, 0);if (max_base_sum == -1) {
    printf("Impossible");}else {
    printf("%d =", N);for (int i = 0; i < K; i++) {
    if (i != 0)printf(" +");printf(" %d^%d", ans[i], P);}}return 0;
}