好久不寫了啊，最近打算重新啟用這個blog。就先寫這個題目吧，滿經典的。
【題目大意】
　　m * n的區域內，每個整數坐標都有整點，問以這些整點為端點能夠形成多少個三角形。（0 < m, n <= 1000）

【題目分析】
　　這個題目乍一看挺簡單的，但是想做對還是要仔細的思考下的。補集轉化的思想，求出所有共線的三元組，然后用總數減掉就是答案了，關鍵就是如何求共線三元組。x坐標相同和y坐標相同的比較好計算，在一條斜線的就不好算了，畫個圖發現，即使斜率相同的線，經過的格點數可能各不相同。思路當然還是枚舉y / x（不同的y / x確定了不同的矩形區域），之后如何有效的計算，我采用的方法可能有些麻煩，有點類容斥的方法。以斜率為a / b為例，(a, b) = g，那么m * n的區域內一定有(m - a + 1) * (n - b + 1)個那么大的矩形，這樣的矩形經過的格點數是(g + 1)；然后因為同等斜率小一點的矩形(a - a / g, b - b / g)也是存在的，個數同樣可以統計出來，但是有些大矩形包括了，要去掉；因此就采用這種思想，先求出大矩形的個數，然后依次往下減，就可以避免重復計數了。雖然這樣復雜度有點高，不過極限數據還是比較快的跑出來了。
　　說的可能不太清楚，具體代碼如下：

這個題目去年就過了，用得是狀態壓縮dp，不過沒用dfs預處理，當時做得不是很明白，還是參考網上的一個代碼做的。
現在重新做了一下這個題目，請教了icecream，學會了一個很簡練的做法，而且比較好理解還好寫。
首先還是狀態的表示，用0表示沒有放木塊，用1表示放了木塊。此外，對于一個橫放的木塊，對應的兩位都用1表示；對于一個豎放的木塊，第一行用1表示，第二行用0表示。這只是一種設狀態的方式，當然還有別的設法，但是這種方法在接下來就會發現優點。

狀態表示完就要處理轉移了，如何判斷一個轉移是否合法比較難辦，用一個dfs卻可以簡潔的解決這個問題。
對于上一行到下一行的轉移，規定上一行一定填滿，這樣有三種方式：
    dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
    dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
    dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
第一種上面是1，那么下面一定是0，表示是一個豎放的木塊。
第二種上面是0，就是說這個位置一定是一個豎放木塊的下半截，那么下一行肯定是要另起一行了，放一個豎放或者橫放的木塊都必須是1。
第三種相當于上下兩行各放一個橫木塊。
實現的時候我用了一個vector記錄每個狀態所有可行的轉移，這樣在dp的時候可以加快一些效率。

還有一個問題需要考慮，那就是初值和最終的結果。如果尋找合法狀態，依然比較麻煩，假設共有n行，可以分別在這n行上下新加兩行。下面一行都是1，由于第n行肯定要填滿，這樣新加的全1的行就相當于頂住了第n行使其沒有凸出（有凸出那么第n+1行有0），而通過第n行到第n+1行轉移保留了所有合法狀態；同理最上面加的那行保證第一行沒有凸出。最后第n+1行對應全1的狀態就是最終的結果了。通過新加行巧妙地解決了初值和終值。

實現的時候也需要注意一下，在TSP問題中，外層循環是狀態，內層是點，之所以這樣寫因為在枚舉點的時候，可能會從比當前編號大的點轉移，但是由于無論怎樣轉移過來的狀態肯定比當前狀態?。ㄈサ袅?），所以先從小到大枚舉狀態就保證轉移過來的狀態一定是算過的。而這個題目里面正好反過來，因為狀態可能從比當前狀態大的狀態轉移過來，而行數肯定是從編號小的行轉移，因此先枚舉行就能保證轉移過來的狀態一定是更新過的。

【題目大意】
　　定義兩個三元組I(xi, yi, zi)和J(xj, yj, zj)，他們的差為D(I, J) = max{xi - xj, yi - yj, zi - zj} - min{xi - xj, yi - yj, zi - zj}，給定n個三元組（n <= 200000），求任意兩個三元組的差的和。

【題目分析】
　　數據范圍非常大，枚舉必然不可，需要數學方法。這個題目巧妙之處在于，模型經過了層層的包裝，要想一下子有想法還真不容易。既然不能枚舉了，這個max和min操作就不好辦了，應該設法去掉。max{a, b, c} - min{a, b, c} = |a - b| + |b - c| + | c - a| / 2，這個公式應該不難想到，但是這只是第一步，因為引進了絕對值，依然不好做。可以先算出分子，最后再除2。接下來需要一個等價變換，以a - b為例，a - b = xi - xj - yi + yj = (xi - yi) - (xj - yj)，同理把b - c、c - a都寫成這種形式。這一步變換看似作用不大，但是假設我們算出所有的xi - yi之后（i = 0... n - 1），將其排序，會發現，對于第i個xi - yi，它前面的都比它小，后面的都比它大。而實際上，由于求任意兩個三元組的差，肯定xi - yi會和任意的xj - yj都作差的，加了絕對值后，它對最后的結果就會貢獻i個(xi - yi)，n - i - 1個-(xi - yi)。同樣的方法算出所有的(yi - zi)和(zi - xi)，結果就能夠求出來了。算法復雜度O(n * logn)。

【題目總結】
　　這是一道不錯的題目，首先考察了公式的變形，需要改寫max - min操作，之后的等價變換和排序的思想都非常值得借鑒。
題目代碼：

　　題目大意是給定n個點的坐標（n <= 10000），問把這些點移動到一橫行并且一個挨著一個（具體位置任意）的最少移動步數（其中每次只能向上下左右移動一個坐標）。
　　這個題目體現了轉化的思想。首先考慮這樣的問題：一個數軸上有n個坐標，問把這n個坐標移動到一個點上最少移動步數，其中每次移動一個格子。根據中位數的定義，把所有坐標排序后第n / 2個坐標是中位數，把所有坐標移動到這上面移動次數最小。證明很容易想到，因為如果不這樣的話，把目標坐標往左平移還是往右平移，勢必造成左半部的坐標集體變化1，右半部的坐標也集體變化1，如果左右半部坐標的個數不同，那么顯然就不是最優的了。
　　接下來考慮題目，題目中x和y的移動是孤立的，可以分開討論。y的移動方法和上面討論的情況一樣，現在考慮x的移動。x的移動要求最終是一個挨著一個的，x排好序之后，假設最終所有點以x0為左端點依次排開，對應的點分別為x0, x1...那么問題的答案就等于把這n個坐標依次對應的挪到x0到xn-1上的步數。如果我們把這n個目標點分別都移動到x0上，那么問題就轉化成了中位數問題了。考慮把xi移動到x0上，要花費i步，為了保證問題是等價變換的，應該把xi在原坐標中對應的xi'也相應的向左移動i步，這樣xi'移動到xi的代價就是不變的。設xi'左移i步后的新位置是xi''，那么問題就轉化成：把x0''到xn-1''這n個點移動到一個坐標的最小步數，用中位數的方法就可以做出來了。
　　這個題目的巧妙之處在于把一個未知問題轉化成一個已知問題。轉化的思想在數學中用的很多，應該多多練習。

題目代碼：

　　給定n個數求這n個數劃分成互不相交的m段的最大m子段和。
　　經典的動態規劃優化的問題。設f(i, j)表示前i個數劃分成j段，且包括第i個數的最大m子段和，那么有dp方程：
　　　　f(i, j) = max { f(i - 1, j) + v[i], max {f(k, j - 1) + v[i]}(k = j - 1 ... i - 1) }
　　也就是說第i個數要么自己劃到第j段，要么和前一個數一起劃到第j段里面，轉移是O(n)的，總復雜度O(n * n * m)。
　　可以引入一個輔助數組來優化轉移。設g(i, j)表示前i個數劃分成j段的最大子段和（注意第i個數未必在j段里面），那么遞推關系如下：
　　　　g(i, j) = max{g(i - 1, j), f(i, j)}，分是否加入第i個數來轉移
　　這樣f的遞推關系就變成：
　　　　f(i, j) = max{f(i - 1, j), g(i - 1, j - 1)} + v[i]，轉移變成了O(1)
　　這樣最后的結果就是g[n][m]，通過引入輔助數組巧妙的優化了轉移。實現的時候可以用一維數組，速度很快。

附HDU 1024題目代碼：