百年一度的太陽棋盛事又要開始了！
也許你會問，什麼是太陽棋呢？太陽棋就是那些掌握宇宙星體運行的神明所下的棋，你也許會想，既然太陽棋是一種棋子，那麼它的本質就應該和我們所玩的棋子相同。沒錯，太陽棋也是在和我們一般所知的棋子一樣是在正方型的二維網格中進行遊戲，只不過，它所用的棋子是宇宙間的恆星 (其實應該正名為"恆星棋"，但是因為我們身處地球，所以就稱為太陽棋啦)。
太陽棋有一項重要的規則，就是神明可以在遊戲開始前先將棋子放在棋盤中自己所想要的格子中。每一格格子都被賦予太陽值(每一格都可能不同，這就是這個遊戲有趣的地方)，如果神明在一開始有將棋子放在此格中，那麼神明就可以獲得此格的太陽值，將有利於之後遊戲的展開，但是請注意，由於這些棋子的本質是恆星，如果兩兩離得太近，那麼棋子將會彼此灼燒，所以對於任一個放在棋盤中的棋子而言，其八方位都不能再有任何棋子。
你、我、還有那些神明都知道，找出所有的擺棋子方法再來計算太陽值的最大值是不可能的(除非你不想 AC 這題)，所以請你用程式幫助神明找出所有方法中太陽值的最大值。
正式地說，給定一個 n × n 的網格，每格裡有一個數字 Vi,j 。 選擇其中若干格使得任兩格在八方位不相鄰(也就是說有公共邊或公共角都不行)， 並求出總和的最大值。
輸入第一行為一正整數 n ，代表太陽棋棋盤的邊長。
接下來輸入 n 行，每一行有 n 個以空格相隔的整數 Vi,j ，代表其中的太陽值。
對於所有滿足 1 ≤ i ≤ n ， 1 ≤ j ≤ n 的 i, j ，都滿足 1 ≤ Vi,j ≤ 106
輸出一整數，代表太陽值總和的最大值。
#test input 1: 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 #test input 2: 3 1 1 100000 1 1 1 100000 1 1 #test input 3: 3 1 1 1 1 20000 1 1 1 1 #test input 4: 3 1 20000 1 1 1 1 1 20000 1
#test output 1: 4 #test output 2: 200002 #test output 3: 20000 #test output 4: 40000
dp, bitmask (CF 2500)
10% 的測資滿足 1 ≤ n ≤ 22，且所有的 Vi,j 都相同
20% 的測資滿足 1 ≤ n ≤ 15
25% 的測資滿足 1 ≤ n ≤ 19
45% 的測資滿足 1 ≤ n ≤ 22
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||