C++의 3n 조각 피자

<시간/>

크기가 다른 3n 조각의 피자가 있다고 가정하면 나와 내 두 친구는 다음과 같이 피자 조각을 가져갈 것입니다. -

피자 조각을 선택하겠습니다.
내 친구 Amal이 내가 선택한 것의 시계 반대 방향으로 다음 슬라이스를 고를 것입니다.
내 친구 Bimal이 내가 선택한 시계 방향으로 다음 슬라이스를 고를 것입니다.
피자 조각이 더 이상 없을 때까지 이 단계를 반복합니다.

피자 조각의 크기는 시계 방향의 원형 배열 조각으로 표시됩니다. 내가 가질 수 있는 슬라이스 크기의 가능한 최대 합을 찾아야 합니다.

따라서 입력이 [9,8,6,1,1,8]과 같으면

C++의 3n 조각 피자

그러면 출력은 16이 됩니다. 각 턴에서 크기가 8인 피자 조각을 선택하기 때문입니다. 내가 크기 9의 슬라이스를 선택하면 내 친구들은 크기 8의 슬라이스를 선택할 것입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

solve() 함수를 정의하면 배열 v와 하나의 인수 m이 필요합니다.

n :=v의 크기
각각 (n + 1) x (m + 1) 크기의 두 개의 2D 배열 dp1 및 dp2 정의
initialize 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 :=슬라이스 크기
ret :=0
ret :=solve(인덱스 1에서 끝까지 슬라이스, n/3) 및 slices[0] + solve(인덱스 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}