CF1364B-B. Most socially-distanced subsequence

題意

給出一個長度為n的數字序列，讓你找出它的一個子序列，長度為k，使得這個子序列的$|s_1?s_2|+|s_2?s_3|+...+|s_{k?1}?s_k|$的值最大且k最小。

---

思路

首先肯定是將全部的數字都算上去這個，這個值會是最大的。但是題目要求k的值最小，所以要將這些數字中對于這個值的增大沒有貢獻的數字去掉。

那么什么樣的數字對于這個值的增大沒有貢獻呢？假如一個有三個數字1、5、9，那么這個5對于這個值的增大就沒有貢獻，因為$|1?5|+|5?9|=|1?9|$；同樣的，若三個數字是$9、5、1$，這里面的5對于數字的增大也沒有貢獻。

綜上，我們就是要把所有的比左邊大比右邊小的數字和比左邊小比右邊大的數字去掉，最終得到的序列就是答案。

---

AC代碼

#include <cstdio> #include <cstring> #include <iostream> #include <vector>std::vector<int>a;void solve() {int n, t;a.clear();scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &t);a.push_back(t);}for (int i = 1; i < a.size() - 1; i++) {if (a[i] > a[i - 1] && a[i] < a[i + 1]) {a.erase(a.begin() + i);i--;} else if (a[i] < a[i - 1] && a[i] > a[i + 1]) {a.erase(a.begin() + i);i--;}}printf("%d\n", (int)a.size());for (int i = 0; i < a.size(); i++) {printf("%d%c", a[i], " \n"[i == a.size() - 1]);} }int main() {int T;scanf("%d", &T);while (T--) {solve();}return 0; }

總結

以上是生活随笔為你收集整理的CF1364B-B. Most socially-distanced sub的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。