শেফের n ডিশের স্যাটিসফ্যাকশন লেভেল দেওয়া আছে। ডিশ কুক করতে ১ ইউনিট টাইম লাগে। Like-time coefficient = time[i] * satisfaction[i]। ডিশগুলো যেকোনো অর্ডারে রান্না করা যায় এবং কিছু ডিশ বাদ দিতে পারা যায়। সর্বোচ্চ Like-time coefficient যোগফল বের করুন।
উদাহরণ: [-1,-7,0,6,-7] -> ১৭ (দ্বিতীয় ও শেষ ডিশ বাদ দিয়ে: -1*1 + 0*2 + 6*3 = 17)।
সমাধানের ধাপসমূহ
- DP মেমোইজেশন: dp[idx][time] = idx থেকে শুরু করে time টাইমে সর্বোচ্চ মান।
- সর্ট করা স্যাটিসফ্যাকশন অ্যারে ব্যবহার করুন।
- solve(idx, time): যদি idx == size, 0।
- ret = max(solve(idx+1, time), v[idx]*time + solve(idx+1, time+1))।
- dp[idx][time] = ret রিটার্ন।
C++ কোড উদাহরণ
#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);
}
};
int main() {
Solution ob;
vector<int> v = {-1,-7,0,6,-7};
cout << ob.maxSatisfaction(v);
return 0;
}
ইনপুট
{-1,-7,0,6,-7}
আউটপুট
17
