不是很難吧，\(30\)分的題。
和1053 Path of Equal Weight (30 分)類似，畢竟都是\(DFS\)，^_^。
給定正整數N、K、P，将N表示成K個正整數(可以相同，遞減排列)的P次方的和，即\(N=n_1^P + \cdots + n_k^P\)，如果有多種方案，那麼選擇底數和\(n_1 +...+ n_k\)最大的方案；如果還有多種方案，那麼選擇底數序列的字典序最大的方案。
跑了\(900ms\)，有點吃緊。
以下為晴神思路：
由于P不小于2，并且在單次運作中是固定的，是以不妨開一個vector fac，在輸入P之後就預處理出所有不超過N的\(n^p\)。為了友善下标與元素有直接的對應，這裡應把0也存進去。于是對N=10、P=2來說，fac[0]=0、fac[1]=1、fac[2]=4、fac[3]=9。
接下來便是DFS函數。DFS用于從fac中選擇若千個數(可以重複選)，使得它們的和等于N。于是需要針對fac 中的每個數，根據選與不選這個數來進入兩個分支，是以DFS的參數中必須有:①目前處理到的是fac的幾号位，不妨記為index；②目前已經選擇了幾個數，不妨記為nowK。由于目的是選出的數之和為N，是以參數中也需要記錄目前選擇出的數之和sum。而為了保證有多個方案時底數之和最小，還需要在參數中記錄目前選擇出的數的底數之和facSum。于是需要的參數就齊全了。
此外，還需要開一個vector ans，用來存放最優的底數序列，而用一個 vector temp來存放目前選中的底數組成的臨時序列。
考慮遞歸本身。注意：為了讓結果能保證字典序大的序列優先被選中，讓index從大到小遞減來周遊，這樣就總是能先選中fac中較大的數了。顯然，如果目前需要對fac[index]進行選擇，那麼就會有“選”與“不選”兩種選擇。如果不選，就可以把問題轉化為對fac[index-1]進行選擇，此時nowK、sum、facSum 均不變；而如果選，由于每個數字可以重複選擇，是以下一步還應當對fac[index]進行選擇，但由于目前選了fac[index]，需要把底數index加入目前序列temp中，同時讓nowK加1、sum加上fac[index]、facSum 加上index。顯然，DFS必須在index不小于1時執行，因為題目求的是正整數的幂次之和。
那麼，遞歸到什麼時候停止呢?首先，如果到了某個時候sum== N并且nowK == k成立，那麼說明找到了一個滿足條件的序列(就是temp，注意儲存的是底數)，此時為了處理多方案的情況，需要判斷底數之和facSum是否比一個全局記錄的最大底數之和maxFacSum更大，若是，則更新maxFacSum，并把temp賦給ans。除此之外，當sum>N或者nowK>K時，不可能會産生答案，可以直接傳回。
多方案時判斷是否更優的做法的時間複雜度最好是\(O(1)\)，否則容易逾時。是以必須在DFS的參數中記錄目前底數之和facSum，避免在找到一組解時計算序列的底數之和。
同①，不要在找到一組解時才判斷temp序列與ans序列的字典序關系，而應該讓index從大到小進行選擇，這樣fac[index]大的就會相對早地被選中。
以下為優化後的代碼，快了一倍多。
