問題概要

整数列 \(A_1,\dots,A_N\) が与えられます。 \(k=1,\dots,\lceil \frac{N}{2} \rceil\) について、以下の問題を解いてください。

• 隣接する要素を同時に選ばないようにちょうど \(k\) 個の要素を選ぶとき、選んだ要素の合計としてあり得る最大値は？

解法

番兵として、先頭と末尾に \(-\infty\) を追加しておきます。

\(A_{i-1} \le A_i \ge A_{i+1}\) のとき、この \(3\) 要素に関して以下のような縮約を考えます。

• この \(3\) 要素を値 \(A_{i-1}-A_i+A_{i+1}\) の \(1\) 要素に置き換え、「隣接を気にせず自由に選べる多重集合 (\(S\) とする)」に \(A_i\) を追加する。

数列の長さが \(2\) 以下になるまで上記の縮約を繰り返すことが出来、そうして出来た \(S\) の要素を降順に選ぶのが最適解となります。

実装

スタックに \(1\) 要素ずつ追加しながら、末尾 \(3\) つが縮約可能なら縮約することを繰り返せば良いです。（縮約後のスタック内は常に単調増加となります）

計算量は sort がネックとなり、\(O(N \log N)\) です。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  
  vector<ll> ans, st = {-INF};
  auto add = [&](ll x) {
    while (st.size() >= 2 && x <= st.back() && st.back() >= st.end()[-2]) {
      ans.push_back(st.back());
      x -= st.back(); st.pop_back();
      x += st.back(); st.pop_back();
    }
    st.push_back(x);
  };
  rep(i,n) add(a[i]);
  add(-INF);
  sort(ans.rbegin(), ans.rend());
  int m = ans.size();
  rep(i,m-1) ans[i+1] += ans[i];
  for (ll x : ans) cout << x << '\n';
  return 0;
}

謝辞

この解法は Elegia 氏の提出 に着想を得たものです。