假设有一个披萨,该披萨的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