Giảm món ăn trong C ++

Giả sử có một đầu bếp. Và anh ta đã thu thập dữ liệu về mức độ hài lòng của n món ăn của mình. Đầu bếp có thể nấu bất kỳ món ăn nào trong 1 đơn vị thời gian. Hệ số thích thời gian của một món ăn thực tế là thời gian thực hiện

nấu món ăn đó bao gồm cả các món trước đó nhân với mức độ hài lòng của nó Sotime [i] * hài lòng [i].

Chúng ta phải tìm tổng tối đa của hệ số Like-time mà người đầu bếp có thể nhận được sau khi chuẩn bị món ăn. Các món ăn có thể sẵn sàng theo bất kỳ thứ tự nào và đầu bếp có thể loại bỏ một số món ăn để nhận được giá trị tối đa này.

Vì vậy, nếu đầu vào là [-1, -7,0,6, -7], thì đầu ra sẽ là 17, Sau khi loại bỏ món ăn thứ hai và cuối cùng, tổng hệ số thích thời gian tối đa sẽ là -1 * 1 + 0 * 2 + 6 * 3 =17.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một mảng dp có kích thước:505 x 505.
Xác định một hàm giải quyết (), điều này sẽ lấy idx, thời gian, một mảng v,
nếu idx bằng với kích thước của v, thì -
- trả về 0
nếu dp [idx, time] không bằng -1 thì -
- trả về dp [idx, time]
ret:=-inf
ret:=tối đa giải (idx + 1, time, v) và v [idx] * time + giải (idx + 1, time + 1, v)
dp [idx, time]:=ret
trả lại ret
Từ phương thức chính, thực hiện như sau -
Điền vào -1 này với dp
sắp xếp mảng v
trả về giải quyết (0, 1, v)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Giảm món ăn trong C ++

Ví dụ

Đầu vào

Đầu ra