สมมติว่ามีพิซซ่าชิ้นหนึ่งที่มีขนาดต่างกัน 3n ชิ้น ฉันและเพื่อนสองคนจะทานพิซซ่าชิ้นหนึ่งดังนี้ −
-
ฉันจะเลือกพิซซ่าชิ้นใดก็ได้
-
Amal เพื่อนของฉันจะเลือกชิ้นถัดไปในทิศทางทวนเข็มนาฬิกาที่ฉันเลือก
-
Bimal เพื่อนของฉันจะเลือกชิ้นถัดไปในทิศทางตามเข็มนาฬิกาที่ฉันเลือก
-
ทำซ้ำขั้นตอนเหล่านี้จนกว่าจะไม่มีชิ้นพิซซ่าอีกต่อไป
ขนาดของชิ้นพิซซ่าจะแสดงด้วยชิ้นอาร์เรย์วงกลมในทิศทางตามเข็มนาฬิกา เราต้องหาผลรวมของขนาดสไลซ์ให้ได้มากที่สุด
ดังนั้น หากอินพุตเป็น [9,8,6,1,1,8],
จากนั้นผลลัพธ์จะเป็น 16 ตามการเลือกชิ้นพิซซ่าขนาด 8 ในแต่ละเทิร์น ถ้าฉันเลือกชิ้นที่มีขนาด 9 เพื่อนของฉันจะเลือกชิ้นที่มีขนาด 8
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
กำหนดฟังก์ชัน Solve() ซึ่งจะใช้อาร์เรย์ v และหนึ่งอาร์กิวเมนต์ m
-
n :=ขนาดของวี
-
กำหนดอาร์เรย์ 2D สองชุด dp1 และ dp2 ของขนาด (n + 1) x (m + 1) แต่ละรายการ
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
สำหรับการเริ่มต้น j :=0 เมื่อ j <=m อัปเดต (เพิ่ม j ขึ้น 1) ทำ −
-
x :=v[i]
-
ถ้า j
-
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 :=ขนาดของชิ้น
-
ยกเลิก :=0
-
ret :=สูงสุดของการแก้ปัญหา (สไลซ์จากดัชนี 1 ถึงจุดสิ้นสุด n/3) และสไลซ์[0] + การแก้ (สไลซ์จากดัชนี 2 ถึงจุดสิ้นสุด - 1, n/3 - 1)
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
