atcoder abc128 D - equeue

AtCoder

問題

D - equeue

解法

操作A-D(問題文より)

  • 操作 A: D に詰められた宝石のうち、左端の宝石を取り出して手に入れる。
  • 操作 B: D に詰められた宝石のうち、右端の宝石を取り出して手に入れる。
  • 操作 C: 持っている宝石を 1 つ選んで D の左端に詰める。
  • 操作 D: 持っている宝石を 1 つ選んで D の右端に詰める。

操作C、Dは持っている宝石から一つを選んで捨てる操作と置き換えると簡単になる。

捨てる操作は最後にまとめて行って良いので、操作A、BをK回以下行うケースをすべて試し、そこから価値がマイナスのものを残った操作回数分捨てればよい

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int n,k;
vector<int> v;

void solve() {
  int ans = 0;

  for (int left = 0; left <= min(k,n); left++) {
    for (int right = 0; right+left <= min(k,n); right++) {
      vector<int> tmp;
      REP(i,left) tmp.push_back(v[i]);
      REP(i,right) tmp.push_back(v[n - i - 1]);

      int tot = 0;
      for(int x: tmp) tot += x; // 価値のトータル算出

      sort(tmp.begin(),tmp.end()); // 持っている宝石を価値の昇順に並べかえ
      REP(i,tmp.size()) { // 宝石を捨てる操作
        if (k-(left+right) <= i) break; // 操作回数の上限
        if (0 <= tmp[i]) break; // 価値が正の宝石は捨てる必要はない
        tot -= tmp[i];
      }
      ans = max(ans, tot);
    }
  }

  cout << ans << endl;
  return;
}

int main() {
  cin >> n >> k;
  v.resize(n);
  REP(i,n) cin >> v[i];

  solve();
  return 0;
}