PAT甲级 1103 Integer Factorization

原题链接

https://pintia.cn/problem-sets/994805342720868352/exam/problems/type/7?problemSetProblemId=994805364711604224&page=1

题目大意

给三个正整数N、K、P，将N表示成K个正整数（可以相同，递减排列）的P次方和，如果有多种方案，选择底数n1+…+nk最大的方案，如果还有多种方案，选择底数序列的字典序最大的方案～

解题思路

先把i从0开始所有i的p次方的值存储在v[i]中（v[i] <= n）。然后用DFS找方案，注意剪枝，详细见代码。

代码（CPP）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl "\n"
const int maxn = 1e3 + 10;
const ll INF = 0x3f3f3f3f3f3f3fLL;
vector<int> nums;
vector<int> tmpAns, ans;
int n, k, p;

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

int MaxFacSum = -1;
void dfs(int index, int curSum, int curK, int facSum) {
    if (curK == k) {
        if (curSum == n && facSum > MaxFacSum) {
            ans = tmpAns;
            MaxFacSum = facSum;
        }
        return;
    }
    if (index == 0) {
        return;
    }
    for (int i = index; i >= 1; i--) {
        if (curSum + nums[i] <= n) {    // 剪枝，如果此时所选数的和已经超过了n，则没必要继续下探搜索了
            tmpAns[curK] = i;
            dfs(i, curSum + nums[i], curK + 1, facSum + i);
        }
    }
}

void solve() {
    cin >> n >> k >> p;
    tmpAns.resize(k);
    init();
    dfs(nums.size() - 1, 0, 0, 0);
    if (MaxFacSum == -1) {
        cout << "Impossible\n";
        return;
    }
    cout << n << " = ";
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0)
            cout << " + ";
        cout << ans[i] << "^" << p;
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}