[AtCoder] ABC 128 D – equeue

2019年5月27日2019年5月28日

問題

方針

操作の順序

操作 A, B を先に行い、残りの操作で C, D を行います。操作 C, D では負の価値の宝石を絶対値の大きい順に筒に詰めていきます。最後にまとめて宝石を戻すということです。

全探索

制約が緩いので全探索を行います。操作 A を行う回数を \( l \)、操作 B を行う回数を \( r \) とすると、\( 0 \leq l + r \leq K \) であり、戻すことができる宝石の数は \( K – (l + r) \) となります。

どのように全探索を行うかですが、操作 A と 操作 B の回数の二重ループで行います。注意する点は、操作 A で宝石を取った宝石は、操作 B で宝石を取ることができないということです。\( N – l \) が残りの宝石数となるので、この値が操作 B で取ることができない宝石が分かります。

コード

提出したコード

全探索

int ans = 0;

  for (int l = 0; l <= K; l++) {
    if (l > N) break;
    vector<int> v1;
    int sum1 = 0;
    for (int i = 0; i < l; i++) {
      sum1 += V[i];
      if (V[i] < 0) v1.push_back(V[i]);
    }
    for (int r = 0; r <= K; r++) {
      if (l + r > K || r > N || N - l < r) break;
      vector<int> v2;
      int sum2 = sum1;
      for (int i = N - 1; i >= N - r; i--) {
        sum2 += V[i];
        if (V[i] < 0) v2.push_back(V[i]);
      }
      copy(v1.begin(), v1.end(), back_inserter(v2));
      sort(v2.begin(), v2.end());
      for (int i = 0; i < K - l - r && i < v2.size(); i++) {
        sum2 += -v2[i];
      }
      ans = max(ans, sum2);
    }