मान लीजिए कोई रसोइया है। और उन्होंने अपने n व्यंजनों के संतुष्टि स्तर पर डेटा एकत्र किया है। शेफ किसी भी डिश को 1 यूनिट समय में बना सकता है। किसी व्यंजन का समान समय गुणांक वास्तव में लिया गया समय होता है
उस व्यंजन को पकाने के लिए जिसमें पिछले व्यंजन को उसके संतुष्टि स्तर से गुणा किया जाता है सोटाइम[i]*संतुष्टि[i]।
हमें समान-समय गुणांक का अधिकतम योग ज्ञात करना होगा जो रसोइया व्यंजन तैयार करने के बाद प्राप्त कर सकता है। व्यंजन किसी भी क्रम में तैयार किए जा सकते हैं और रसोइया इस अधिकतम मूल्य को प्राप्त करने के लिए कुछ व्यंजनों को त्याग सकता है।
इसलिए, यदि इनपुट [-1,-7,0,6,-7] जैसा है, तो आउटपुट 17 होगा, दूसरी और आखिरी डिश को हटाने के बाद, अधिकतम कुल समान-समय गुणांक -1*1 + होगा 0*2 + 6*3 =17.
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
आकार की dp सरणी परिभाषित करें:505 x 505।
-
फ़ंक्शन हल करें () को परिभाषित करें, इसमें idx, समय, एक सरणी v,
लगेगा -
यदि idx, v के आकार के समान है, तो -
-
वापसी 0
-
-
अगर dp[idx, time] -1 के बराबर नहीं है, तो -
-
वापसी डीपी [आईडीएक्स, समय]
-
-
रिट:=-इन्फ
-
रिट:=अधिकतम हल (आईडीएक्स + 1, समय, वी) और वी [आईडीएक्स] * समय + हल (आईडीएक्स + 1, समय + 1, वी)
-
डीपी [आईडीएक्स, समय]:=सेवानिवृत्त
-
वापसी रिट
-
मुख्य विधि से निम्न कार्य करें -
-
इस -1 को dp से भरें
-
सरणी को क्रमबद्ध करें v
-
वापसी हल (0, 1, वी)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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