首页 > 代码库 > PAT甲题题解-1103. Integer Factorization (30)-(dfs)
PAT甲题题解-1103. Integer Factorization (30)-(dfs)
该题还不错~。
题意:给定N、K、P,使得可以分解成N = n1^P + … nk^P的形式,如果可以,输出sum(ni)最大的划分,如果sum一样,输出序列较大的那个。否则输出Impossible。
dfs枚举,为了防止超时,这里要预先将从1开始的i^p的值存储在factor数组中,直到i^p>n。然后dfs深度优先搜索,相当于把问题一步步分解,即若第一个因子是n1,则接下来我们要判断N-n1^p、k-1是否可行。同时存储当前因子的总和sum,要取sum最大的;还有上一次相加的因子的索引last,因为因子要从大到小输出,所以后一个不能大于前一个因子。
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <cmath> using namespace std; /* 其实可以预先把i^p<n的i都存储起来 */ const int maxn=405; int res[maxn]; int ans[maxn]; int factor[maxn]; int fidx=0; int maxsum=0; bool flag=false; int n,k,p; /* num为当前的总和 cnt为还剩几个i^p项,即当前的k sum为各因子的总和,因为要取和最大的 last为上一个因子的索引,因为要保证因子从大到小输出, 所以dfs后一个因子在factor中的索引不能大于上一个 */ void dfs(int num,int cnt,int sum,int last){ if(num==0&&cnt==0){ if(sum>maxsum){ flag=true; for(int i=1;i<=k;i++) ans[i]=res[i]; maxsum=sum; } return; } else if(cnt==0) return; for(int i=min(fidx-1,last);i>=0;i--){ int left=num-factor[i]; if(left>=cnt-1){ res[cnt]=i+1; dfs(left,cnt-1,sum+i+1,i); } } } int main() { scanf("%d %d %d",&n,&k,&p); int tmp=1; fidx=0; //预先存储i^p<=n的i while(tmp<=n){ factor[fidx]=tmp; fidx++; tmp=pow(fidx+1,p); } int cnt=0; int last=fidx-1; dfs(n,k,0,last); if(flag){ printf("%d =",n); for(int i=k;i>=2;i--){ printf(" %d^%d +",ans[i],p); } printf(" %d^%d",ans[1],p); } else{ printf("Impossible"); } return 0; }
PAT甲题题解-1103. Integer Factorization (30)-(dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。