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