PAT 甲级 刷题日记|A 1103 Integer Factorization (30 分) 样例4 5分析

思路

本题是深搜的一个应用：排列组合，选取给定的序列中的部分数字（可重复选择）使得满足给定条件。放到本题中：给定序列，从1到x（x是第一个p次大于等于n的数），满足条件：每项的p次和为n.

组合按照非增序排列，若有多组，选择和最大的一组结果。若结果仍不唯一，选择两组数字中，第一个不相等元素中较大的那个组合。例如9 9 7 6；9 9 7 3；，第一个不相等的元素为6和3 选择6 的元素的那个组合。

同时，考虑到pow运算多次重复，可以使用打表的技巧，以减少用时，通过样例5。

样例四的数据应该类似 23 1 1.

和力扣39 40 一样，建议没思路的同学可以先做力扣

代码

#include <bits/stdc++.h>
using namespace std;

int n, k, p;
const int maxn = 403;
int power[maxn];
vector<int> nums, num2;
vector<int> ans;
int maxsum = 0;

void dfs(int len, int target, int idx, int numsum, vector<int>& combine) {
    if (idx >= nums.size()) return;
    if (len == 0 && target == 0) {
        if (numsum >= maxsum) {
            ans = combine;
            maxsum = numsum;
        } 
        return;
    } else if(len == 0 || target == 0) {
        return;
    }
    dfs(len, target, idx + 1, numsum, combine); //no
    if (power[nums[idx]] <= target) {
        combine.push_back(nums[idx]);
        target -= power[nums[idx]];
        len -= 1;
        numsum += nums[idx];
        dfs(len, target, idx, numsum, combine);
        numsum -= nums[idx];
        len += 1;
        target += power[nums[idx]];
        combine.pop_back();
    }
    
}

int main() {
    cin>>n>>k>>p;
    for (int i = 1; i <= n; i++) {
        power[i] = pow(i, p);
        if (power[i] > n) break;
        num2.push_back(i);
    }
    for (int i = num2.size() - 1; i >= 0; i--) {
        nums.push_back(num2[i]);
    }
    vector<int> combine;
    dfs(k, n, 0, 0, combine);
    if (ans.size() == 0) {
        cout<<"Impossible"<<endl;
        return 0;
    }
    cout<<n<<" =";
    for (int i = 0; i < k; i++) {
        printf(" %d^%d", ans[i], p);
        if (i != k - 1) printf(" +");
    }
     
}