本文正體字版由OpenCC轉換

【問題分析】

枚舉答案轉化爲判定性問題，然後最小路徑覆蓋，可以轉化成二分圖最大匹配，從而用最大流解決。

【建模方法】

枚舉答案A，在圖中建立節點1..A。如果對於i<j有i+j爲一個完全平方數，連接一條有向邊(i,j)。該圖是有向無環圖，求最小路徑覆蓋。如果剛好滿足最小路徑覆蓋數等於N，那麼A是一個可行解，在所有可行解中找到最大的A，即爲最優解。

具體方法可以順序枚舉A的值，當最小路徑覆蓋數剛好大於N時終止，A-1就是最優解。

【建模分析】

由於是順序放球，每根柱子上的球滿足這樣的特徵，即下面的球編號小於上面球的編號。抽象成圖，把每個球看作一個頂點，就是編號較小的頂點向編號較大的頂點連接邊，條件是兩個球可以相鄰，即編號之和爲完全平方數。每根柱子看做一條路徑，N根柱子要覆蓋掉所有點，一個解就是一個路徑覆蓋。

最小路徑覆蓋數隨球的數量遞增不遞減，滿足單調性，所以可以枚舉答案（或二分答案），對於特定的答案求出最小路徑覆蓋數，一個可行解就是最小路徑覆蓋數等於N的答案，求出最大的可行解就是最優解。本問題更適合枚舉答案而不是二分答案，因爲如果順序枚舉答案，每次只需要在殘量網絡上增加新的節點和邊，再增廣一次即可。如果二分答案，就需要每次重新建圖，大大增加了時間複雜度。

魔術球問題
問題描述: 假設有 n 根柱子,現要按下述規則在這 n 根柱子中依次放入編號爲 1,2,3,...的球。
(1)每次只能在某根柱子的最上面放球。
(2)在同一根柱子中,任何 2 個相鄰球的編號之和爲完全平方數。
試設計一個算法,計算出在 n 根柱子上最多能放多少個球。例如,在 4 根柱子上最多可放 11 個球。
́編程任務:
對於給定的 n,計算在 n 根柱子上最多能放多少個球。
數據輸入: 由文件 input.txt 提供輸入數據。文件第 1 行有 1 個正整數 n,表示柱子數。
結果輸出: 程序運行結束時,將 n 根柱子上最多能放的球數以及相應的放置方案輸出到文件output.txt 中。文件的第一行是球數。接下來的 n 行,每行是一根柱子上的球的編號。
輸入文件示例
input.txt
4
輸出文件示例
output.txt
11
1 8
2 7 9
3 6 10
4 5 11

上次修改時間 2017-02-03