题解：P5978 [CEOI 2018] Global warming

第一眼的思路肯定是把序列分成

3

段：

[1,l),[l,r],(r,n]

。然后从三段中各取一个最长上升子序列拼起来。

然后注意到，对于这样一个方案，如果把最后一段

(r,n]

也加上

d

，显然答案不会下降。因此实际上只需要把序列分成

2

段，分别求最长上升子序列拼起来。

再贪心一下发现第二段直接加

x

不劣的。

最长上升子序列的求法参考 P1020 导弹拦截。

总之我们可以求出两个数组

p

和

s

：

p_i

表示以第

i

个元素结尾时的最长上升子序列长度，

s_i

表示以第

i

个元素开头时的最长上升子序列长度。

然后从前往后扫一遍，对于每个位置

i

，计算

s_i+\max\limits_{j\lt i,a_j\lt a_i+x} p_{j}

即可。

随便用数据结构维护一下就行了。

Code

CPP

#include <bits/stdc++.h>
using namespace std;

template <typename T, typename Compare = less<T>> class LongestIncreasingSubsequence {
public:
  vector<size_t> last;

  LongestIncreasingSubsequence(size_t size, const T &maxx, const T &minn) : last(size + 1, maxx) {
    last[0] = minn;
  }

  size_t insert(const T &value) {
    constexpr Compare comp{};
    auto it = lower_bound(last.begin(), last.end(), value, comp);
    *it = value;
    return distance(last.begin(), it);
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);

  size_t n;
  int64_t x;
  cin >> n >> x;

  vector<int64_t> arr(n);
  for (size_t i = 0; i < n; ++i)
    cin >> arr[i];

  vector<size_t> suffix(n);
  {
    LongestIncreasingSubsequence<int64_t, greater<int64_t>> LIS(n, INT64_MIN, INT64_MAX);
    for (size_t i = n - 1; ~i; --i)
      suffix[i] = LIS.insert(arr[i]);
  }

  size_t ans = suffix[0];
  multiset<pair<int64_t, size_t>> last;
  LongestIncreasingSubsequence<int64_t> LIS(n, INT64_MAX, INT64_MIN);
  for (size_t i = 1; i < n; ++i) {
    {
      size_t len = LIS.insert(arr[i - 1]);
      auto it = last.emplace(arr[i - 1], len);
      pair<int64_t, size_t> curr = *it;
      for (++it; it != last.end(); it = last.erase(it))
        if (it->second > curr.second)
          break;
    }
    {
      auto it = last.lower_bound({arr[i] + x, 0});
      if (it == last.begin())
        continue;
      --it;
      ans = max(ans, it->second + suffix[i]);
    }
  }
  cout << ans << '\n';
  return 0;
}

题解：P5978 [CEOI 2018] Global warming

文章操作

相关推荐

评论

题解：P5978 [CEOI 2018] Global warming