C++で配列から要素を削除することによって取得できる最大ポイントを見つけます

コンセプト

N個の要素と2つの整数lおよびrを持つ特定の配列Aに関して、1≤a _x ≤10 ⁵ 1≤l≤r≤N。配列の任意の要素（たとえばax）を選択して削除できます。また、a _xに等しいすべての要素を削除することもできます。 + 1、a _x +2…a_x +Rおよびa_x -1、a _x -2…a_x -配列からの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-1、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