[数据结构与算法]1103 Integer Factorization (30 分)【难度: 中 / 爆搜】

https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224
爆搜的做法，动态规划也可以做，有时间也一个动态规划的做法。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int ve[N],path[N],ans[N];
int maxv,n,k,p,i;
void dfs(int sum,int s,int cnt,int pos)
{
    if(sum>n) return;
    if(cnt==k&&sum==n)
    {
        if(s>maxv) 
        {   
            memcpy(ans,path,sizeof ans);
            maxv=s;
        }
        return;
    }
    while(pos>0)
    {
        path[cnt]=pos;
            if(sum+ve[pos]<=n&&cnt+1<=k) dfs(sum+ve[pos],s+pos,cnt+1,pos);
        pos--;
    }
}
int main(void)
{
    cin>>n>>k>>p;
    for(i=1;i<=n;i++)
        if(pow(i,p)<=n) ve[i]=pow(i,p);
        else break;
    dfs(0,0,0,i-1);//从大到小搜
    if(maxv) 
    {
        cout<<n<<" = ";
    	for(int j=0;j<k;j++) 
    	{
        	if(j) cout<<" + ";
        	printf("%d^%d",ans[j],p);
    	}
    }else puts("Impossible");
    return 0;
}