1935 . [APIO '15]Palembang Bridges
TopCoder
Description
巨港市被穆西河分成兩區。假設這兩區分別是A區和B區，每區分別都有1,000,000,001棟建築分布在河的兩邊，方便起見編號為0到1,000,000,000。任兩棟相鄰的建築距離為1單位。河寬也是1單位。A區中第i棟建築恰好位於B區中第i棟建築的對面。有$N$個市民住在城市中。第i位市民的房子在$P_i$區第$S_i$棟建築，而他的公司在$Q_i$區第$T_i$棟建築。如果某個市民從他房子到他公司必須經過一條河，那麼他就必須要搭船。這非常不方便，所以政府決定要蓋最多$K$座橫跨河面的橋讓市民們可以只要開車不用搭船就可以去工作。每座橋一定要連結兩個在不同側的建築並與河垂直。除此之外，橋之間不能覆蓋彼此。假設$D_i$是第$i$位市民從他家開車到他的公司所需要開的最短距離，請幫助政府建橋使得$D_1+D_2+\dots+D_N$最小。
Input Format
第一行包含兩個整數$K,N$。接下來的$N$行中每一行都有四個代碼$P_i,S_i,Q_i,T_i$。
對於所有測資，$P_i,Q_i$是字元A,B中的一者，$0\leq S_1,T_i\leq 1000,000,000$，且可以有超過一個房子或公司(或兩者)同時在同一棟建築物裡。
第一組測資佔分8分，且$K=1,1\leq N\leq 1,000$。
第二組測資佔分14分，且$K=1,1\leq N\leq 100,000$。
第三組測資佔分9分，且$K=2,1\leq N\leq 100$。
第四組測資佔分32分，且$K=2,1\leq N\leq 1,000$。
第五組測資佔分37分，且$K=2,1\leq N\leq 100,000$。
Output Format
請輸出一行包含距離總和的最小值。
Sample Input 1
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
Sample Output 1
Sample Input 2
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
Sample Output 2
Hints
第一個範例測資中，在編號4的建築物之間蓋一座橋是其中一個最佳策略。
第二個範例測資中，在編號2和6的建築物之間蓋橋是其中一個最佳策略。
Problem Source
2015 APIO pC.
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~10 | 8 |
| 2 | 11~20 | 14 |
| 3 | 21~32 | 9 |
| 4 | 33~44 | 32 |
| 5 | 45~56 | 37 |