給你一個序列A，請你把序列A分成連續K個子段，每個子段的代價是 sum(A[i]*A[j]) 其中 i < j。請問如何分組使代價最小。

    數據范圍|A|,K <1000

吐槽：

    cppblog的editor可真是不咋的...  昨天弄了一下午LyX，想用XeTeX編譯，結果屢屢失敗。用vim寫的TeX文檔是可以用XeTeX編譯并正確顯示中文的。但是不知道為什么用LyX寫就不可以.... 有沒有TeX高手來指點一下啊...

解法分析：

    首先狀態轉移方程比較容易想到:DP[i][k]表示前i項分成了k組，那么有DP[i][k] = max(DP[j][k-1]+cost[j+1][i])對所有 j < i;

    這是一個2D/1D的方程，時間復雜度是O(n^3)，對于n = 1000來說必然超時，需要優化...

    (A[j]+...+A[i])^2 = A[j]^2 + A[j+1]^2 + ... + A[i]^2 + 2* cost[j][i]; (沒有TeX寫這個就是不爽啊)
    于是乎 cost[j+1][i] = ((sum[i]-sum[j])^2 - suma[i] + suma[j])/2 = -sum[i] * sum[j] + (suma[j] - sum[j]^2)/2 + (sum[i]^2 - suma[i])/2;
    終于把這個轉成只和 i,j相關的表達式了， 可以斜率優化了：
    X(j) = sum[j]
    Y(j) = (suma[j] - sum[j]^2)/2 + dp[j][k-1];
    C(i) = (sum[i]^2 - suma[i])/2
    我們要求的是 dp[i][k] = -sum[j]*X(j) + Y(j) + C(i);
    移項得 Y(j) = X(j)*sum[j] + dp[i][k] - C(i) 轉成了線性規劃問題。 不難想到最優解一定在凸包上。
    而且X,Y是單調的，可以用棧維護凸包。斜率是單調的，可以用隊列維護最優決策。
代碼部分：