tioj 1449 郵局設置問題EXTREME

第50個解題報告，寫點好玩的東西

四邊形不等式

他是一個用來優化DP的一個好工具

DP有一些專用術語： tD / eD

子問題數目為O( n^t )個，每個子問題要依賴於 O( n^e )個子問題

總時間複雜度是O( n^(t+e) )。

這裡碰到的是最常見的2D/1D優化－四邊形不等式－

通常2D/1D的遞移式長得像這樣：C( i, j ) = opt{ C( i, k-1 ) + C( k, j ) + w( i, j ) }

照理來說是O(n^3)，但可以優化成為O(n^2)！！！

但有一個必要的條件，C[a,c]+C[b,d] <= C[a,d]+C[b,c]（a<b<c<d）

當有了這個條件，便會產生一個可怕的定理：

若i, j 的最佳斷點為K[i][j]，則 K[i][j-1]<=K[i][j]<=K[i+1][j]。

遞移式變成：C[i,j]=opt{ C[i,k-1] + C[k,j] } ( s[i,j-1] ≤ k ≤ s[i+1,j] )

複雜度：(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n] -s[nL,n-1])=s[n-L+1,n]-s[1,L] ≤ n

接下來就要來證明那個強大的定理。

為了方便書寫，定義：mk[ i, j ] = C[ i, k ]+C[ k, j ]，K[ i, j ] = d。

目前擁有兩個關係：

(1) C[a,c]+C[b,d] <= C[a,d]+C[b,c]      和     (2) 若k<d，則C[ i, k ] + C[ k, j ] >= C[ i, d ]+C[ d, j ]

如果 當k<d，則 C[ i+1, k ] + C[ k, j ] >= C[ i+1, d ] + C[ d, j ] ，那 d <= K[ i+1 ][ j ] 成立。

因為C滿足四邊形不等式，那C[ i+1, k ]+C[ i, d ] ≥ C[ i+1, d ]+C[ i, k ]（i<i+1<k<d）

-> ( C[ i+1, k ]+C[ i, d ] ) - ( C[ i+1, d ]+C[ i, k ] ) >= 0

-> ( C[ i+1, k ] + C[ k, j ] + C[ i, d ] + C[ d, j ] ) - ( C[ i+1, d ] + C[ d , j ] + C[ i, k ] + C[ k, j ]) >= 0

-> ( ( C[ i+1, k ]+C[ k, j ] )-( C[ i+1, d ] + C[ d , j ] ) )-( ( C[ i, k ]+C[ k, j ] )-(  C[ i, d ]+C[ d, j ] ) ) >= 0

-> ( C[ i+1, k ] + C[ k, j ] ) - ( C[ i+1, d ] + C[ d, j ] ) >= 0

-> C[ i+1, k ] + C[ k, j ] >= C[ i+1, d ] + C[ d, j ] ，QED。

同理可證，K[i][j-1] <= K[i][j]，故 K[i][j-1]<=K[i][j]<=K[i+1][j]。

剛剛證的是普遍性的遞移式會符合，但平常碰到實質的題目，要自己重證一下比較好。

這提可以透過遞迴，以O(n^2)的時間複雜度求得對某區段中，設一郵局的最近距離和。

（定義為w[ i ][ j ] ）

遞移式：w[ i ][ j ] = w[ i ][ j-1 ] + v[ j ] - v[ ( i + j ) / 2 ]

由這個遞移式就可以推得 w 符合凸四邊形不等式，且符合區域單調性。

所以C也符合四邊形不等式，所以就可以用那個優化變成O(n^2)。

code: http://codepad.org/LSfUIY9m