題目連結
題意還是很好了解的，樸素版本的DFS也是很容易寫出的（如169 5 2，第一個基底選12的話，就變成子問題25 4 2了，解決子問題可以遞歸，第一個基底不斷縮小最小到1可以得到其他的情況），K的大小就是dfs 的最深的層次，從大到小枚舉基底，基底的上界一開始想的是拿N的根p次方，如169 5 2的話就是從13開始枚舉，沒有進行剪枝時連樣例169 167 3都無法在規定時間跑完，但是送出上去還是能拿23分的，說明陳越外婆還是很仁慈的。
從中定義了int getFirst(int N)函數，用來獲得N的根p次方的值，定義了快速幂kPow(int base,int n)函數計算 b a s e n base^n basen,這是最開始的思路，進行了下面的4處剪枝/優化： （當然這些值其實可以打表的）
以上四處改動才逐漸把分數拿滿，第一處的剪枝保證了諸如樣例169 167 3這種能過，因為從大的底數進行查找，當 169 = 5 3 + . . . . 169= 5^3 +.... 169=53+...., 如果沒有這層剪枝，将會一直搜尋下去，會 169 = 5 3 + 2 3 + 1 3 + 1 3 . . . . 169= 5^3 +2^3+1^3+1^3.... 169=53+23+13+13....,但是此時因為125+（167-1）已經超過169了，也就是說剩下的166個空位，全部是 1 3 1^3 13都不能等于169，更何況程式還會嘗試 2 3 2^3 23,更有甚者會自由組合以下1和2，又會很多情況，但是因為都是沒用的情況是以可以減掉。修改之後可以拿到24分/25分 不記得了。
·
·
·
第二處改動解決了樣例5和6MLE的問題（成功将測試樣例5轉為TLE），一開始為了檢查dfs的正确性，使用vector< vector < int >>類型的變量存儲所有的最終結果，然後再周遊一遍找到符合題意的輸出，但是因為有很多使得等式成立的組合，全部存下來會爆記憶體，鑒于是從大到小的尋找基底，是以可以邊比較邊存儲，因為對于sum相同的情況，肯定首先遇到像6 6 6 6 5這樣的情況（因為從大都小尋找基底），是以隻要tempTop>top時更新答案即可，不需要先搜到所有答案再進行排序比較，這也說明了要巧妙利用dfs搜尋的順序。
·
·
·
第四處改動
在搜尋過程中會出現諸如10 6 4 4 1，10 4 4 6 1， 10 1 4 4 6等，這些無非是這幾個數字的自由組合，對最終答案沒有影響，因為是從大到小搜尋基底的，是以隻需要對下一個基底≤上一個基底的基低進行dfs，因為後者大于前者的情況肯定被搜尋過了。有了以上三處改動就能保證25分了，隻有測試樣例5會逾時。
·
·
·
第三處改動解決的最難的測試樣例5和6，即拿滿30分。一開始寫的是base=getFirst(N),這樣的開端其實是最大的，對于400 100 2這種，開局就base=17，跑到猴年馬月。鑒于答案都是相差不大的數字，是以想到了平均值，讓初始base=getFirst(N/K),想着均勻分到N/K,再開p次根号，然後再從大于這個結果的數開始進行查找，這樣雖然很完美的解決了400 100 2，但是送出之後隻得了3分，說明起點太小了，後來又嘗試base=(getFirst(N/K)+getFirst(N))/2也是3分,base=(getFirst(N/K)+2* getFirst(N))/3 (隻在main函數修改，dfs中保持getFirst(N))這樣能得27分（測試樣例6得到2分，測試樣例5還是TLE），相應的把dfs中base也改成(getFirst(N/K)+2 *getFirst(N))/3 就隻能4分了，這說明可以優化的地方确實是這個起始點，但是這樣不斷試錯肯定考試的時候心态會爆炸啊，于是先出去取快遞，在路上想到可不可以直接用N/K作為起點，想了想1<P≤7，P沒取到1，而N/K恰好就是K個位置每個位置是N/K的一次方，（N/K,N/K,N/K,N/K,N/K…N/K）這相對于最終的答案也是一個比較大的起點，因為每個位置至少還要平方，加和會大于N，從這個起始點進行搜尋，dfs到最深層會從最右邊不斷縮小基底，不會漏掉可行解，回到家送出果然AC了！開心！可以安心看其他大佬的題解了嘿嘿
值得一提的是，main中base=N/K dfs中base=getFirst(N) 通過測試樣例5為1000ms+，main中base=N/K,dfs中base=N/（N-depth）（對于子問題，也是先拿平均值也就是一次方作為尋找的上界）測試樣例5就是300ms，可以看到一開始自己找的那個起點有多辣雞嗚嗚，改用這種平均值作為起點之後，相應的getFirst()函數的使命也就結束了。
終于AC的代碼：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int kPow(int base,int n){//計算base的n次方，快速幂闆子
int ans=1;
while(n){
if(n&1==1) ans*=base;
n=n>>1;
base=base*base;
}
return ans;
}
int K,P;//全局變量，省去dfs的時候傳參
vector<int> ans(405,0);
vector<int> RES;//記錄最終答案
int getFirst(int N){//求P次根号，恰好開出來取整，否則取第一個小于此數的
int ans=1;
for(ans=1;ans<=N;ans++){
if(kPow(ans,P)>=N)
break;
}
if(kPow(ans,P)==N) return ans;//恰好開出來取整
else return ans-1;//否則取第一個p次方小于此數的
}
int top=0,tempTop=0;//記錄最大值和臨時最大值
void dfs(int N,int depth){
if(N<0 || N<K-depth) return ;//剩餘的都用1都不行，那剩下的不用嘗試了
if(N>0 && depth >=K) return ;
if(N==0 && depth < K) return ;
if(N==0 && depth == K) {
if(tempTop > top){//因為從大往小找，是以會首先遇到正确答案，邊找邊比較就可行了
top=tempTop;
RES=ans;
}
return;
}
int base=0;
for(base=N/(K-depth);base>=1;base--){//base和main統一起來，對于子問題，也是先拿平均值也就是一次方作為尋找的上界
ans[depth]=base;
tempTop+=base;
if(base<=ans[depth-1])//隻dfs後一項小于等于前一項的，比如10 6 4 4 1會dfs，但是10 4 6 4 1不會，有效剪枝
dfs(N-kPow(base,P),depth+1);
tempTop-=base;
}
}
int main() {
int N;
cin >> N >> K >> P;
int depth=0,base=0;
for(base=N/K;base>=1;base--){//開始用的getFirst(N),測試5會逾時,改成N/K才能通過
ans[depth]=base;
tempTop+=base;
dfs(N-kPow(base,P),depth+1);
tempTop-=base;
}
if(top==0) cout << "Impossible";
else{//按照要求輸出
cout << N << " = ";
for(int i=0;i<K;i++){
cout << RES[i] << "^" << P;
if(i!=K-1){
cout << " + ";
}
}
}
return 0;
}