PAT甲级1103.

目录

A1103

题目

样例

样例1

输入:

169 5 2

输出:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

样例2

输入:

169 167 3

输出:

Impossible

思路和坑点

  这里的代码借鉴了柳神的代码。对一个树进行因式分解,这里使用打表的方法,构造从1~i的p次方数组。然后按照因子的从大到小的方式dfs搜索,知道找到一组可分解的结果,如果结果并列,则按照因子和的大小进行优化。(由于按照因子从大到小的结果进行的搜索,所以满足组合的大小关系要求中的大的序列优先考虑为答案)

AC代码

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<set>
using namespace std;
int n,k,p,maxfacsum=-1;
vector<int> v,ans,tempans;
void init();
void dfs(int index,int tempsum,int tempk,int facsum);
int main(void)
{
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt","r",stdin);
    #endif
    scanf("%d%d%d",&n,&k,&p);       //输入 
    init();                         //初始化1~i的p次方数组 
    tempans.resize(k);              //答案数组大小初始化为k 
    dfs(v.size()-1,0,0,0);          //dfs求解,从最大的p次方项开始,因此第一个参数为v.size-1 
    if(maxfacsum==-1){              //如果没有这样的解,则maxfacsum不变 
        puts("Impossible");
    }
    else{                           //否则输出ans中的结果 
        printf("%d = ",n);
        for(int i=0;i<ans.size();i++){
            if(i) printf(" + ");
            printf("%d^%d",ans[i],p);
        }
    }
    return 0;
}
void init()                         //初始化1~i的p次方数组
{
    int i=1;
    v.push_back(0);                 //下标0位置的占位 
    while(1){
        int temp=pow(i,p);
        if(temp>n)                  //分解的每一个p次方项需要小于n,故以n为界进行初始化 
            break;
        v.push_back(temp);          //讲相应的p次方存入数组中 
        i++;
    }
}
//index 为p次方数组的下标,也就代表了分解的一项的因子 
//tempsum为当前求解的的因子p次方的总和,tempk为当前求解的个数,facsun为因子总和 
void dfs(int index,int tempsum,int tempk,int facsum)    
{
    if(tempk==k){                           //递归边界,得到k个因子 
        if(tempsum==n&&facsum>maxfacsum){   //如果满足分解要求,则保留因子和最大的结果 
            ans=tempans;                    //保存结果 
            maxfacsum=facsum;               //更新因子最大和的数值 
        }
            return ;                        //该层递归结束 
    } 
    while(index>=1){                        
        if(tempsum+v[index]<=n){            //有于因子可以重复,故当循环选择当前的因子,直至不满足要求 
            tempans[tempk]=index;           //想临时结果数组中存放一个p次方项 
            dfs(index,tempsum+v[index],tempk+1,facsum+index); 
        }
        index--;                            // 不满足要求时,从大到小选择下一个因子 
    }
}