1、題目來源：Taejon Regional Contest 2001者：情況： 我只會(huì)搜索，而且極限數(shù)據(jù)還很慢理由：想知道有沒有多項(xiàng)式做法。例如圖論方法，有幾種方法建立模型，但是這些模型都無法解決（有的模型還叫不出名字）。如果是搜索，希望找到一個(gè)對(duì)于極限數(shù)據(jù)也比較快的方法。另外，如果用圖論做的話，或性。以利用本題中圖的特殊Square DestroyerThe left figure below shows a complete 3*3 grid made with 24 matchsticks. The lengths of allmatchsticks are one. You can fi

2、nd many squares of different sizeshe grid. The size of asquare is the length of ite.he grid shownhe left figure, there are 9 squares of sizeone, 4 squares of size two, and 1 square of size three.Eaatchstick of the complete grid is identified wiunique number which is assignedfrom left to right and fr

3、om top to bottom as shown in the left figure. If you take someatchsticks out from the complete grid, then some squareshe grid will be destroyed, whichresults in anplete 3*3 grid. The right figure illustrates anplete 3*3 grid afterremoving three matchsticks numbered with 12, 17 and 23. This removal d

4、estroys 5 squares ofsize one, 3 squares of size two, and 1 square of size three. Consequently, theplete griddoes notwo.ve squares of size three, but still has 4 squares of size one and 1 square of sizeplete) n*n grid made with no moren 2n(n+1)As input, you are given a (complete ormatchsticks for a n

5、atural number n5 .Your task is to compute the minimum number ofmatchsticks taken out to destroy all the squares existinghe input n*n grid.InputThe inponsists ofT test cases. The number of test cases (T ) is givenheline ofthe input file. Each test case consists of two lines: Theline contains a natura

6、l number n ,not greatern 5, which imps you are given a (complete orplete) n*n grid as input,nonnegativeeger k , the number of matchsticksand the second line begins wit aremissing from the complete n*n grid, followed by k numbers specifying the matchsticks. Note t if k is equal to zero, then the inpu

7、t grid is a complete n*n grid; otherwise, the input gridplete n*n grid sucht the specified k matchsticks are missing from the completeis ann*n grid.OutputPrexactly one line for each test case. The line should contain the minimum number ofmatchsticksve to be taken out to destroy all the squareshe inp

8、ut grid.S2203le Input3 12 17 23Output for the S33le Input破壞正方形下邊的圖(a)是一個(gè)用 2*(3*4)=24 根長度為 1長度的火柴棍拼成的完整的 3*3 方格陣。可以看出方格陣中存在許多不同規(guī)模的正方形（正方形的規(guī)模是指其邊的長度）?？梢钥闯鲈趫D(a)中的方格陣?yán)?，?9 個(gè)規(guī)模 1 的正方形，4 個(gè)規(guī)模 2 的正方形和 1 個(gè)規(guī)模 3 的正方形。(a)(b)如圖(a)所示，完整的方格陣中的每根火柴棍都可以用一個(gè)唯一的來區(qū)分，從上到下從左往右逐漸增加。如果你從完整的方格陣中拿出一些火柴棍，這個(gè)方格陣中的一些正方形將被破壞，你將得到一個(gè)不完全的 3*3 方格陣。圖(b)是一個(gè)去掉了分別為 12、17和 23 的 3 火柴棍之后剩下的不完全的 3*3 方格陣。去掉這些火柴棍破壞了 5 個(gè)規(guī)模 1 的正方形，3 個(gè)規(guī)模 2 的正方形和 1 個(gè)規(guī)模 3 的正方形。從而，剩下的不完全方格陣沒有了規(guī)模