HDU 3480 Division 斜率優化 DP 詳解

三重循環 O(M N²) 超時，需優化。

斜率優化推導

設 k1 < k2 < j，若 k1 優於 k2：

dp[i-1][k1] + (a[j]-a[k1+1])² ≤ dp[i-1][k2] + (a[j]-a[k2+1])²

整理得：

(dp[i-1][k1] + a[k1+1]² - dp[i-1][k2] - a[k2+1]²) / (a[k1+1] - a[k2+1]) ≤ 2a[j]

令 y(k) = dp[i-1][k] + a[k+1]², x(k) = a[k+1]，即斜率 (y1-y2)/(x1-x2) ≤ 2a[j]。

維護下凸包（單調隊列）：

• 決策單調性：a[j] 遞增，隊首斜率若 ≤ 2a[j] 則彈出
• 凸包維護：新點入隊時，若尾部兩點與新點形成凹角（斜率不增）則彈出尾點

滾動數組優化空間

int dp[2][MAXN], q[MAXN];
for (int i = 1; i <= m; i++) {
    head = 0; tail = -1; q[++tail] = i-1;
    for (int j = i; j <= n; j++) {
        while (head < tail) {
            int k1 = q[head+1], k2 = q[head];
            if ((dp[turn][k1]+a[k1+1]*a[k1+1] - dp[turn][k2]-a[k2+1]*a[k2+1]) 
                <= 2*a[j]*(a[k1+1]-a[k2+1])) head++;
            else break;
        }
        dp[turn^1][j] = dp[turn][q[head]] + (a[j]-a[q[head]+1])*(a[j]-a[q[head]+1]);
        while (head < tail) {
            int k1 = q[tail], k2 = q[tail-1];
            ll dy1 = dp[turn][j]+a[j+1]*a[j+1] - dp[turn][k1]-a[k1+1]*a[k1+1];
            ll dx1 = a[j+1] - a[k1+1];
            ll dy2 = dp[turn][k1]+a[k1+1]*a[k1+1] - dp[turn][k2]-a[k2+1]*a[k2+1];
            ll dx2 = a[k1+1] - a[k2+1];
            if (dy1*dx2 <= dy2*dx1) tail--;
            else break;
        }
        q[++tail] = j;
    }
    turn ^= 1;
}

時間複雜度降為 O(M N)，空間 O(N)。