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<bits/stdc++.h>
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--;                            // 不满足要求时，从大到小选择下一个因子 
    }
}