การลดจานใน C++

สมมุติว่ามีพ่อครัว และเขาได้รวบรวมข้อมูลเกี่ยวกับระดับความพึงพอใจของอาหารจานเดียวของเขา เชฟสามารถปรุงอาหารจานใดก็ได้ใน 1 หน่วย ค่าสัมประสิทธิ์เวลาเท่ากันของจานคือระยะเวลาที่ใช้จริง

เพื่อปรุงอาหารจานนั้นรวมทั้งจานก่อนหน้าคูณด้วยระดับความพึงพอใจ Sotime[i]*satisfaction[i].

เราต้องหาผลรวมสูงสุดของค่าสัมประสิทธิ์ Like-time ที่เชฟจะได้รับหลังการเตรียมอาหาร สามารถสั่งอาหารตามลำดับใดก็ได้ และเชฟสามารถทิ้งอาหารบางจานเพื่อให้ได้มูลค่าสูงสุด

ดังนั้น หากอินพุตเป็น [-1,-7,0,6,-7] ผลลัพธ์จะเป็น 17 หลังจากลบจานที่สองและจานสุดท้าย ค่าสัมประสิทธิ์เวลาไลค์สูงสุดจะเท่ากับ -1*1 + 0*2 + 6*3 =17.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดขนาดอาร์เรย์ dp:505 x 505

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้เวลา idx, เวลา, อาร์เรย์ v,

• ถ้า idx เท่ากับขนาดของ v แล้ว −

  • คืนค่า 0

• ถ้า dp[idx, time] ไม่เท่ากับ -1 แล้ว −

  • ส่งคืน dp[idx, เวลา]

• ret :=-inf

• ret :=สูงสุดของการแก้ปัญหา (idx + 1, เวลา, v) และ v[idx] * เวลา + การแก้ปัญหา (idx + 1, เวลา + 1, v)

• dp[idx, time] :=ยกเลิก

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• เติม -1 นี้ด้วย dp

• จัดเรียงอาร์เรย์ v

• กลับแก้(0, 1, v)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int dp[505][505];
   int solve(int idx, int time, vector <int>& v){
      if(idx == v.size()) return 0;
      if(dp[idx][time] != -1) return dp[idx][time];
      int ret = INT_MIN;
      ret = max(solve(idx + 1, time, v), v[idx] * time + solve(idx
      + 1, time + 1, v));
      return dp[idx][time] = ret;
   }
   int maxSatisfaction(vector<int>& v) {
      memset(dp, -1, sizeof(dp));
      sort(v.begin(), v.end());
      return solve(0, 1, v);
   }
};
main(){
   Solution ob;
   vector<int> v = {-1,-7,0,6,-7};
   cout << (ob.maxSatisfaction(v));
}

อินพุต

{-1,-7,0,6,-7}

ผลลัพธ์

17