หาคะแนนสูงสุดจากการลบองค์ประกอบออกจากอาร์เรย์ใน C++

แนวคิด

เมื่อได้รับอาร์เรย์ A ที่มี N องค์ประกอบ และจำนวนเต็มสองจำนวน l และ r โดยที่ 1≤ a_x ≤ 10⁵ และ 1≤ l≤ r≤ N เราสามารถเลือกองค์ประกอบใดๆ ของอาร์เรย์ (สมมติว่าเป็น a_x) และลบมันออก รวมถึงลบองค์ประกอบทั้งหมดที่เท่ากับ a_x+1, a_x+2 … a_x+R และ a_x-1, a_x-2 … a_x-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 ถูกลบ ตอนนี้เราจะใช้ Dynamic Programming เพื่อเก็บผลลัพธ์ขององค์ประกอบที่ถูกลบก่อนหน้านี้และนำไปใช้ต่อ

ตัวอย่างโค้ด

// โปรแกรม C++ เพื่อหาค่าใช้จ่ายสูงสุดหลังจาก // ลบองค์ประกอบทั้งหมดออกจากอาร์เรย์ #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<<"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