資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
