給$n$家公司的座標，需要配置$k(k\le \lfloor{\frac{n}{2}}\rfloor)$個電纜，每個電纜必須連接兩家不同公司且每家公司只能被最多一條電纜相連。
求可達到的最小電纜總長。
$2\le n\le 10^5, 0\le a_i<a_{i+1}\le 10^9\ \forall 1\le i<n$
查了解才知道怎麼做，因為是APIO題可以查到很多解><
首先觀察到每條電纜肯定是連相鄰的兩家公司，否則你總是可以將它拆成比較小的。
這樣就有一個很好想的dp，令$dp[n][k]$為考慮第前$n$個點且已經連$k$條的最小成本，則
$$dp[n][k] = min(dp[n - 1][k], dp[n - 2][k - 1] + (a[n]-a[n-1]))$$
這樣就是一個$\mathcal{O}(NK)$的解，可以撈到60分。
至於滿分解，可以考慮greedy，每次不斷取最短距離的兩家公司，取過的不取。
而範側很佛心地告訴你這會爛。
2 1 2 6，如果取1後只能取6，然而更佳解是取2+2。
想一下為什麼這個會爛?
因為我們取了1之後旁邊兩個就不能取了，且對於當前最短的那條，如果他不取，那他左右兩條肯定會取(否則就能取最短這條來達成更佳解)。
因此我們要設計一個「反悔」的機會。
考慮相鄰三條a b c(b < a,c)，取了b，連一條權重為a+c-b的邊在左右，代表改變方案。
然後就用pq不斷維護最小值，而連邊操作會改變每個點的左右是誰，所以用一個雙向的Linked List維護。
複雜度$\mathcal{O}(N+KlogN)$
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
struct seg {
int a, b, dis;
friend bool operator<(seg ca, seg cb) { return ca.dis > cb.dis; }
};
signed main() { EmiliaMyWife
int n, k;
ll ans = 0;
cin >> n >> k;
vector<int> arr(n), nxt(n), prv(n), dis(n);
vector<bool> use(n);
for(int i = 0; i < n; i++)
cin >> arr[i], nxt[i] = i + 1, prv[i] = i - 1;
priority_queue<seg> pq;
for(int i = 1; i < n; i++)
pq.push({i - 1, i, dis[i] = arr[i] - arr[i - 1]});
while(k > 0) {
auto w = pq.top();
pq.pop();
if(use[w.a] || use[w.b])
continue;
ans += w.dis;
k--;
use[w.a] = use[w.b] = 1;
int l = prv[w.a], r = nxt[w.b];
if(l<0 || r==n)
continue;
dis[r] = dis[r] + dis[w.a] - w.dis;
nxt[l] = r;
prv[r] = l;
pq.push({l, r, dis[r]});
}
cout << ans << '\n';
}
|