Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 배열에서 요소를 삭제하여 얻을 수 있는 최대 포인트 찾기

<시간/>

컨셉

N개의 요소와 2개의 정수 l 및 r을 갖는 주어진 배열 A에 대해 1≤ ax ≤ 10 5 및 1≤ l≤ r≤ N. 배열의 모든 요소(ax라고 가정)를 선택하고 삭제할 수 있으며, ax와 같은 모든 요소도 삭제할 수 있습니다. +1, ax +2 ... ax +R 및 ax -1, ax -2 ... ax -L 배열에서. 이 단계에는 도끼 점수가 필요합니다. 우리의 임무는 배열에서 모든 요소를 ​​삭제한 후 총 비용을 최대화하는 것입니다.

입력

2 1 2 3 2 2 1
l = 1, r = 1

출력

8

여기에서 삭제할 2를 선택한 다음, 주어진 l 및 r 범위에 대해 각각 (2-1)=1 및 (2+1)=3을 삭제해야 합니다.

2가 완전히 제거될 때까지 이 작업을 반복합니다. 따라서 총 비용 =2*4 =8입니다.

입력

2 4 2 10 5
l = 1, r = 2

출력

18

여기에서 삭제할 2를 선택한 다음 5를 선택한 다음 10을 선택합니다.

따라서 총 비용 =2*2 + 5 + 10 =19입니다.

방법

이제 모든 요소의 개수를 결정할 것입니다. 요소 X가 선택되었다고 가정하면 [X-l, X+r] 범위의 대립 요소가 삭제됩니다. 현재 랜드 r에서 최소 범위를 선택하고 요소 X가 선택될 때 삭제할 요소를 결정합니다. 결과는 이전에 삭제된 요소의 최대값이며 요소 X가 삭제된 경우입니다. 이제 이전에 삭제된 요소의 결과를 저장하고 추가로 구현하는 동적 프로그래밍을 구현합니다.

예시

// C++ program to find maximum cost after
// deleting all the elements form the array
#include <bits/stdc++.h>
using namespace std;
// Shows function to return maximum cost obtained
int maxCost(int a[], int m, int L, int R){
   int mx1 = 0, k1;
   // Determine maximum element of the array.
   for (int p = 0; p < m; ++p)
      mx1 = max(mx1, a[p]);
   // Used to initialize count of all elements to zero.
   int count1[mx1 + 1];
   memset(count1, 0, sizeof(count1));
   // Compute frequency of all elements of array.
   for (int p = 0; p < m; p++)
      count1[a[p]]++;
   // Used to store cost of deleted elements.
   int res1[mx1 + 1];
   res1[0] = 0;
   // Choosing minimum range from L and R.
   L = min(L, R);
   for (int num1 = 1; num1 <= mx1; num1++) {
      // Determines upto which elements are to be
      // deleted when element num is selected.
      k1 = max(num1 - L - 1, 0);
      // Obtain maximum when selecting element num or not.
      res1[num1] = max(res1[num1 - 1], num1 * count1[num1] +
      res1[k1]);
   }
   return res1[mx1];
}
// Driver program
int main(){
   int a1[] = { 1, 1, 3, 3, 3, 2, 4 }, l1 = 1, r1 = 1;
   int a2[] = { 2, 4, 2, 10, 5 }, l2 = 1, r2 = 2;
   // size of array
   int n1 = sizeof(a1) / sizeof(a1[0]);
   int n2 = sizeof(a2) / sizeof(a2[0]);
   // function call to find maximum cost
   cout<<"Maximum Cost for First Example:" << maxCost(a1, n1, l1,r1)<<endl;
   cout<<"Maximum Cost for Second Example:" << maxCost(a2, n2, l2,r2);
   return 0;
}

출력

Maximum Cost for First Example:11
Maximum Cost for Second Example:19