C ++中具有3n切片的披萨

假设有一个披萨,该披萨的3n片大小不一,我和我的两个朋友将按照以下方式切片披萨-

  • 我将挑选任何披萨片。

  • 我的朋友Amal将按我的选择的逆时针方向选择下一个切片。

  • 我的朋友Bimal将按照我的选择顺时针方向选择下一个切片。

  • 重复这些步骤,直到不再有匹萨饼。

披萨片的大小由顺时针方向上的圆形阵列片表示。我们必须找到我可以拥有的最大切片大小总和。

因此,如果输入类似于[9,8,6,1,1,8],


那么输出将为16,因为每回合选择大小为8的披萨片。如果我选择9号片,我的朋友们将选择8号片。

为了解决这个问题,我们将遵循以下步骤-

定义一个函数solve(),它将接受一个数组v和一个参数m,

  • n:= v的大小

  • 分别定义两个大小为(n + 1)x(m +1)的2D数组dp1和dp2

  • 对于初始化i:= 0,当i <n时,更新(将i增加1),执行-

    • x:= v [i]

    • 如果j <m,则-

    • 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]的最大值

    • 对于初始化j:= 0,当j <= m时,更新(将j增加1),执行-

    • 返回dp1 [n,m]和dp2 [n,m]的最大值

    • 从主要方法中执行以下操作-

    • n:=切片的大小

    • ret:= 0

    • ret:=求解的最大值(从索引1到结尾的切片,n / 3)和slices [0] +求解(从索引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