查找可以通过从C ++中删除数组中的元素获得的最大点数

Z时代
2024-01-10
分类：综合

概念

对于具有N个单元和两个整数L和R，其中，1≤一给定阵列A的_X ≤10 ⁵和1≤L≤R≤N.我们可以选择阵列中的任何元件（比方说AX），并删除它，并从数组中删除等于_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

输出结果

在这里，我们选择2删除，则分别对于给定的l和r范围，将需要删除(2-1)= 1和（2 + 1）= 3。

重复此过程，直到2被完全删除。因此，总成本= 2 * 4 = 8。

输入值

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

输出结果

在这里，我们选择2删除，然后选择5再选择10。

因此总成本= 2 * 2 + 5 + 10 = 19。

方法

现在，我们将确定所有元素的数量。假设选择了元素X，则将删除[Xl，X + r]范围内的所有元素。目前，我们从l和r中选择最小范围，并确定选择元素X时要删除的元素。结果将是先前删除的元素以及删除元素X时的最大值。现在，我们将实现动态编程，以存储先前删除的元素的结果并进一步实现。

示例

// C++ program to find maximum cost after
//删除数组中的所有元素
#include <bits/stdc++.h>
using namespace std;
//显示函数返回获得的最大成本
int maxCost(int a[], int m, int L, int R){
   int mx1 = 0, k1;
   //确定数组的最大元素。
   for (int p = 0; p < m; ++p)
      mx1 = max(mx1, a[p]);
   //用于将所有元素的计数初始化为零。
   int count1[mx1 + 1];
   memset(count1, 0, sizeof(count1));
   //计算数组所有元素的频率。
   for (int p = 0; p < m; p++)
      count1[a[p]]++;
   //用于存储已删除元素的成本。
   int res1[mx1 + 1];
   res1[0] = 0;
   //从L和R中选择最小范围。-
   L = min(L, R);
   for (int num1 = 1; num1 <= mx1; num1++) {
      //确定最多要包含哪些元素
      //选择元素num时删除。
      k1 = max(num1 - L - 1, 0);
      //是否选择元素num时获得最大值。
      res1[num1] = max(res1[num1 - 1], num1 * count1[num1] +
      res1[k1]);
   }
   return res1[mx1];
}
//驱动程序
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;
   //数组大小
   int n1 = sizeof(a1) / sizeof(a1[0]);
   int n2 = sizeof(a2) / sizeof(a2[0]);
   //函数调用以查找最大成本
   cout<<"第一个示例的最高费用：" << maxCost(a1, n1, l1,r1)<<endl;
   cout<<"第二个示例的最高费用：" << maxCost(a2, n2, l2,r2);
   return 0;
}