数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中 3n 片披萨
假设有一个披萨，切成 3n 片，每片大小不一。我和我两个朋友将按照以下方式取披萨片：
我将选择任意一片披萨。
我的朋友 Amal 将选择我选择的披萨片逆时针方向的下一片。
我的朋友 Bimal 将选择我选择的披萨片顺时针方向的下一片。
重复这些步骤，直到没有更多的披萨片。
披萨片的尺寸由顺时针方向的循环数组 slices 表示。我们需要找到我可能获得的最大披萨片尺寸总和。
因此，如果输入类似于 [9, 8, 6, 1, 1, 8]，
则输出将是 16，因为每次选择尺寸为 8 的披萨片。如果我选择尺寸为 9 的披萨片，我的朋友将选择尺寸为 8 的披萨片。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 solve()，它将接收一个数组 v 和一个参数 m，
n := v 的大小
定义两个大小为 (n + 1) x (m + 1) 的二维数组 dp1 和 dp2
初始化 i := 0，当 i < n 时，更新 (i 加 1)，执行：
初始化 j := 0，当 j <= m 时，更新 (j 加 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] 的最大值
返回 dp1[n, m] 和 dp2[n, m] 的最大值
从主方法执行以下操作：
n := slices 的大小
ret := 0
ret := solve(从索引 1 到末尾的 slices，n/3) 和 slices[0] + solve(从索引 2 到末尾 - 1 的 slices，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
262 次查看
