![The chips](https://tioj.ck.tp.edu.tw/pimgs/1316.png)
現在有許多個晶片排成一列,其中兩兩希望連成一對(但一對晶片不一定相鄰),如下圖所示。
然而一個小小(其實不小)的問題是,由於空間關係,晶片間的連線最多只能列上方一條,列下方一條
也就是同一個鉛直位置最多只有兩條連線經過。
試問給定一列晶片的配對條件,在符合上述連線方式的情況下,最多可以連接幾對晶片?
給$2N$個數字,每個數字剛好出現兩次且介於$[1,N], N\le 4000$
考慮貪心,只要走到了某個數字第二次出現就拿(如果可以的話),沒那麼嚴謹的證明大概就是接下來的右界都會在更右邊,如果取了那些右界卻不取比較前面的,答案不會比較好。
時間複雜度$\mathcal{O}(N^2)$
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
|
#include <bits/stdc++.h> using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
signed main() { EmiliaMyWife
int n, ans = 0; cin >> n; vector<int> arr(2 * n), cnt(2 * n), has(n + 1, -1); for(int i = 0; i < n * 2; i++) cin >> arr[i]; for(int i = 0; i < n * 2; i++) { if(~has[arr[i]]) { bool res = 1; for(int j = has[arr[i]]; j <= i; j++) res &= (cnt[j] < 2); if(res) { ans++; for(int j = has[arr[i]]; j <= i; j++) cnt[j]++; } } else has[arr[i]] = i; } cout << ans << '\n';
return 0; }
|