PAT甲级1103Integer Factorization

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224

题解

题目要求

• 正整数N的K-P因数分解就是把N写成K个整数的P次幂之和。

• 输入

  • N：不超过400，
  • K：不超过N
  • P：大于1，不超过7

• 输出

  按格式输出K个整数

解题思路

DFS+剪枝

思路是按照柳神题解来的，我可真是个菜鸡┭┮﹏┭┮。

题目样例一的输出似乎是错的诶。

代码

// Problem: PAT Advanced 1103
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224
// Tags: DFS 剪枝

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n, k, p, maxFacSum = -1;
vector<int> v, ans, tempAns;

void init() {
    int temp = 0, index = 1;
    while (temp <= n) {
        v.push_back(temp);
        temp = pow(index, p);
        index++;
    }
}

void dfs(int index, int tempSum,int tempK, int facSum){
    if (tempK == k){
        if (tempSum == n && facSum > maxFacSum){
            ans = tempAns;
            maxFacSum = facSum;
        }
        return;
    }

    while (index >= 1){
        if (tempSum + v[index] <= n){
            tempAns[tempK] = index;
            dfs(index, tempSum + v[index], tempK + 1, facSum + index);
        }
        if (index == 1) return;
        index--;
    }
}

int main()
{
    scanf("%d %d %d", &n, &k, &p);
    init();
    tempAns.resize(k);
    dfs(v.size() - 1, 0, 0, 0);
    if (maxFacSum == -1){
        printf("Impossible");
        return 0;
    }
    printf("%d = %d^%d", n, ans[0], p);
    for(int i = 1; i < ans.size(); i++)
        printf(" + %d^%d", ans[i], p);
    return 0;
}

参考链接

https://blog.csdn.net/liuchuo/article/details/52493390

---

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

---