請從編程挑戰賽2009年

Question

解釋這個算法這是問題的round 1B 2009 Problem C "Square Math"。我知道比賽分析已發佈。但是當一個節點可以被訪問多次時，我沒有得到如何實現BFS。我只能實現使用DFS。 （因爲上下文被隱式保存在遞歸DFS中）。如何使用BFS做到這一點？

Answer 1

你必須明確地保存上下文。

對於每個編號單元，保持可以由在該小區結束的長度N路徑來生產，並且對於每個總，產生它的最佳路徑所有總量的表。對於N = 1，這個數據很容易產生（每個單元一條簡單的路徑）並且給定N的表，通過擴展每條路徑，可以很容易地生成下一個更大的N的表。