C++で3nスライスのピザ

さまざまなサイズの3nスライスのピザがあるとすると、私と2人の友人は次のようにピザのスライスを取ります-

• ピザのスライスを選びます。

• 友達のアマルが私のピックの反時計回りに次のスライスをピックします。

• 友達のBimalが、私のピックの時計回りに次のスライスをピックします。

• ピザのスライスがなくなるまで、これらの手順を繰り返します。

ピザスライスのサイズは、時計回りの円形配列スライスで表されます。可能な最大のスライスサイズの合計を見つける必要があります。

したがって、入力が[9,8,6,1,1,8]のような場合、

次に、各ターンでサイズ8のピザスライスを選択すると、出力は16になります。サイズ9のスライスを選ぶと、友達はサイズ8のスライスを選びます。

これを解決するには、次の手順に従います-

関数solve（）を定義します。これは、配列vと1つの引数mを取ります。

• n：=vのサイズ

• それぞれサイズ（n + 1）x（m + 1）の2つの2D配列dp1とdp2を定義します

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j <=mの場合、更新（jを1増やします）、実行-

    • x：=v [i]

    • j

      • dp2 [i + 1、j +1]=最大dp2[i+ 1、j +1]およびdp1[i、j] + x）

      • dp1 [i + 1、j]=最大dp1[i + 1、j]、dp2 [i、j]およびdp1 [i、j]

• dp1 [n、m]およびdp2 [n、m]

  の最大値を返します

• メインの方法から、次のようにします-

• n：=スライスのサイズ

• ret：=0

• ret：=solve（インデックス1から最後までのスライス、n / 3）とslices [0] +solve（インデックス2から最後までのスライス-1、n / 3-1）の最大値

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector <int> v, int m){
      int n = v.size();
      vector<vector<int> > dp1(n + 1, vector<int>(m + 1));
      vector<vector<int> > dp2(n + 1, vector<int>(m + 1));
      for (int i = 0; i < n; i++) {
         for (int j = 0; j <= m; j++) {
            int x = v[i];
            if (j < m)
            dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp1[i]
            [j] + x);
            dp1[i + 1][j] = max({ dp1[i + 1][j], dp2[i][j],
            dp1[i][j] });
         }
      }
      return max(dp1[n][m], dp2[n][m]);
   }
   int maxSizeSlices(vector<int>& slices) {
      int n = slices.size();
      int ret = 0;
      ret = max(solve(vector<int>(slices.begin() + 1,
      slices.end()), n / 3), slices[0] + solve(vector<int>(slices.begin() +
      2, slices.end() - 1), n / 3 - 1));
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {9,8,6,1,1,8};
   cout << (ob.maxSizeSlices(v));
}

入力

{9,8,6,1,1,8}

出力

16