Code 備忘錄►DP

TIOJ::1449 . 郵局設置問題EXTREME

http://tioj.ck.tp.edu.tw/problems/1449
這題是DP，而且要用到四邊形不等式優化。
Code很短，可是證明真的超難的QQ。

這題題目給你N個數線上的房子，你可以把其中M個變成郵局，求所有房子到他最近的郵局的距離和最小是多少。

解法很簡單，如果只有一間郵局的時候，就選中位數當作郵局就可以了。
假如 $ w(i,j) $ 是[i,j]之間只有一間郵局的情況下，[i,j]之間的最短距離和是多少，我們可以得到DP轉移式：
$$ w(i,j) = w(i,j-1) + v(j) - v((i+j)/2) $$ 其中V(i)是第 i 棟房子的 x 座標，仔細推導一下就可以發現這個式子很神奇的會對。

所以先用$ O(N^2) $ 求出 $ w(i,j) $，然後假設$ dp(i,j) $ 是有 i 間郵局的情況下，[0,j]區間的答案是多少，我們可以得到轉移式：
$$ dp(i,j) = min \lbrace dp(i-1,k) + w(k+1, j)\ | i-1 \leq k \leq j-1 \rbrace $$ 也就是[0,k]區間中有i-1間郵局和[k+1,j]區間中有一間郵局的和的最小值。

這個DP式是$ O(N^3) $，但是可以用四邊形不等式優化成$ O(N^2) $，證明在這裡。

總之我們可以透過四邊形不等式得到一個條件： $ K(i-1,j) \leq K(i,j) \leq K(i,j+1) $ ，其中$K(i,j)$是轉移$dp(i,j)$時最好的 k ，也就是說，要是我已經轉移了第一個和第三個區間([i-1,j]、[i,j+1])，那我現在要嘗試的 k 就不用從 i-1 到 j-1，而是可以從$ K(i-1,j) $ 到 $ K(i,j+1) $ ，對於所有$ j-i = c $的複雜度就是：
$$ \sum_{0\leq i < N-c} K(i,j+1) - K(i-1,j) = O(N)$$ ，非常神奇。

這裡證明一下 $ dp(i,j) $ 會滿足四邊形不等式 $ f(a,c) + f(b,d) \leq f(b,c) + f(a,d); (a<b<c<d)$。
先證式1： $ w(i,j) + w(i+1,j+1) \leq w(i+1,j) + w(i,j+1); (i<i+1<j<j+1)$
若式1不成立，
式1 $ \Rightarrow w(i,j) + w(i+1,j) + v(j+1) - v((i+1+j+1)/2) \leq w(i+1,j) + w(i,j) + v(j+1) - v((i+j+1)/2) $
$ \Rightarrow -v((i+1+j+1)/2) \leq -v((i+j+1)/2) $
$ \Rightarrow v((i+j)/2+1) \geq v((i+j)/2) $ ，也會不成立，但是這和$ v(i) \leq v(i+1) $ 矛盾，
所以$ w(i,j) $ 符合四邊形不等式。

式2：$ dp(i,j) + dp(i+1,j+1) \leq dp(i+1,j) + dp(i,j+1) $
待補

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 1001;
int D[N], W[N][N], DP[N][N], K[N][N];
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    Fl(i,2,n+1)cin>>D[i];
    sort(D+1,D+n+1);
    Fl(i,1,n+1)Fl(j,i+1,n+1){
        W[i][j] = W[i][j-1] + D[j] - D[(i+j)/2];
    }
    Fl(i,1,n+1)DP[1][i] = W[1][i];
    Fl(i,2,m+1){
        K[i][n+1] = n-1;
        for(int j = n;j>=i;j--){
            int &now = DP[i][j], &k1 = K[i-1][j], &k2 = K[i][j+1];
            now = 2147483647;
            Fl(k,k1,k2+1){
                int tmp = DP[i-1][k] + W[k+1][j];
                if(now > tmp)now = tmp, K[i][j] = k;
            }
        }
    }
    cout<<DP[m][n]<<endl;
}