৩n স্লাইসের পিজা আছে। আমি এবং দুই বন্ধু পালাবদলে নিব: আমি যেকোনো একটা, আমল এন্টি-ক্লকওয়াইজ, বিমল ক্লকওয়াইজ। সর্বোচ্চ কত আকারের স্লাইস আমি পেতে পারি তা বের করুন।
উদাহরণ: [9,8,6,1,1,8] -> ১৬ (প্রতিবার ৮ আকারের স্লাইস নিলে)।
সমাধানের ধাপসমূহ
- সার্কুলার অ্যারে -> লিনিয়ার করতে দুটি কেস: প্রথম স্লাইস নেই, বা প্রথম স্লাইস নেওয়া।
- solve(v, m): DP দিয়ে m টি স্লাইস নেওয়ার সর্বোচ্চ যোগফল। dp1[i][j] = i-তম পর্যন্ত j টি নেওয়া নেই, dp2[i][j] = i-তম নেওয়া।
- ট্রানজিশন: dp2[i+1][j+1] = max(dp2[i+1][j+1], dp1[i][j]+v[i])। dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j], dp2[i][j])।
- উত্তর = max(solve(slices[1:], n/3), slices[0] + solve(slices[2:-1], n/3-1))।
C++ কোড উদাহরণ
#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 = 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;
}
};
int main() {
Solution ob;
vector<int> v = {9,8,6,1,1,8};
cout << ob.maxSizeSlices(v);
return 0;
}
ইনপুট
{9,8,6,1,1,8}
আউটপুট
16
