Codeforces-1682 C: LIS or Reverse LIS?

題目傳送門：Codeforces-1682 C: LIS or Reverse LIS?

題目

題目截圖

樣例描述

題目大意

? 給定一個數(shù)組 $a$，可以調(diào)整其任意順序。令 $LIS(?)$ 為最長上升（嚴(yán)格）子序列，$a^{\prime }$ 為反轉(zhuǎn) $a$ 后得到的數(shù)組，求 $\min (LIS(a),LIS(a^{\prime }))$。

題目解析

? 如果學(xué)過 LIS，里面有一種做法，從一個空數(shù)組（結(jié)果數(shù)組）開始，用二分替換的方式求一個給定數(shù)組的 LIS，其核心思想是插入數(shù)值，讓結(jié)果數(shù)組變得更優(yōu)，這道題也是屬于利用插入。
? 一個顯然的性質(zhì)是：反轉(zhuǎn)數(shù)組的最長上升（嚴(yán)格）子序列就是原數(shù)組的最長下降（嚴(yán)格）子序列，顯然，這兩個最多只能有一個下標(biāo)的交集。
? 因此，對數(shù)組中有重復(fù)的數(shù)字，我們可以將它放入上升和下降兩個子序列中（更多的同一重復(fù)數(shù)字沒有作用）。那么沒有重復(fù)的數(shù)字，我們就可以將它們等量地插入進(jìn)這兩個子序列中。當(dāng)這個沒有重復(fù)的數(shù)字個數(shù) $t$ 是奇數(shù)個時，我們可以將它當(dāng)作兩個序列公共的那個數(shù)字，因此答案只需要再加上一個有重復(fù)的數(shù)字個數(shù) $s$。最終結(jié)果是：$s+?\frac{t}{2}?$。

Code

#include <bits/stdc++.h> using namespace std;int main() {int T, n;cin >> T;while(T--) {cin >> n;vector<int> a(n); map<int, int> M;for(int& i : a) cin >> i, ++M[i];int s = 0, t = 0;for(auto& [i, j] : M) t += (j == 1), s += (j > 1);cout << s + ((t + 1) / 2) << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces-1682 C: LIS or Reverse LIS? 【构造】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。