資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢從陣列中刪除元素可以獲得的最大點數
概念
對於給定的包含 N 個元素的陣列 A 以及兩個整數 l 和 r，其中 1≤ ax ≤ 105 且 1≤ l≤ r≤ N。我們可以選擇陣列中的任何元素（假設為 ax）並將其刪除，並且還刪除陣列中等於 ax+1、ax+2 … ax+R 和 ax-1、ax-2 … ax-L 的所有元素。此步驟將花費 ax 分。我們的任務是在刪除陣列中的所有元素後最大化總成本。
輸入
2 1 2 3 2 2 1 l = 1, r = 1
輸出
8
在這裡，我們選擇 2 進行刪除，然後 (2-1)=1 和 (2+1)=3 將需要根據給定的 l 和 r 範圍分別刪除。
重複此操作，直到 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] 中的所有元素。目前，我們從 l 和 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
更新於： 2020-07-25
102 次檢視
廣告