ধরুন একজন শেফ আছে। এবং তিনি তার এন ডিশের সন্তুষ্টি স্তরের তথ্য সংগ্রহ করেছেন। শেফ 1 ইউনিট সময়ে যেকোনো খাবার রান্না করতে পারেন। একটি খাবারের লাইক-টাইম কোফিসিয়েন্ট আসলে নেওয়া সময়
পূর্ববর্তী খাবারগুলি সহ সেই থালা রান্না করার জন্য এর সন্তুষ্টির স্তর Sotime[i]*তৃপ্তি[i] দ্বারা গুণিত।
আমাদের লাইক-টাইম সহগের সর্বাধিক যোগফল খুঁজে বের করতে হবে যা শেফ খাবার তৈরির পরে পেতে পারে। খাবার যেকোন ক্রমে প্রস্তুত হতে পারে এবং শেফ এই সর্বোচ্চ মান পেতে কিছু খাবার ফেলে দিতে পারেন।
সুতরাং, যদি ইনপুটটি [-1,-7,0,6,-7] এর মত হয়, তাহলে আউটপুট হবে 17, দ্বিতীয় এবং শেষ ডিশটি সরানোর পরে, সর্বাধিক মোট লাইক-টাইম সহগ হবে -1*1 + 0*2 + 6*3 =17।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:505 x 505।
-
একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এতে idx, সময়, একটি অ্যারে v,
লাগবে -
যদি idx v এর আকারের সমান হয়, তাহলে −
-
ফেরত 0
-
-
যদি dp[idx, time] -1 এর সমান না হয়, তাহলে −
-
dp[idx, time]
ফেরত দিন
-
-
ret :=-inf
-
ret :=সমাধানের সর্বাধিক (idx + 1, সময়, v) এবং v[idx] * সময় + সমাধান (idx + 1, সময় + 1, v)
-
dp[idx, time] :=ret
-
রিটার্ন রিটার্ন
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
dp
দিয়ে এই -1টি পূরণ করুন -
অ্যারে সাজান 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
