मान लीजिए कि हमारे पास शब्दों की एक सूची है, एकल अक्षरों की एक सूची है और प्रत्येक वर्ण के लिए अंक हैं। हमें दिए गए अक्षरों का उपयोग करके बनाए गए शब्दों के किसी भी मान्य सेट का अधिकतम अंक प्राप्त करना है।
हम अक्षरों में सभी वर्णों का उपयोग नहीं कर सकते हैं और प्रत्येक अक्षर का उपयोग केवल एक बार किया जा सकता है। 'ए', 'बी', 'सी', ..., 'जेड' अक्षरों का स्कोर क्रमशः स्कोर [0], स्कोर [1], ..., स्कोर [25] द्वारा दिया जाता है।
इसलिए, यदि इनपुट शब्दों की तरह है =["भगवान", "अच्छा", "टोक", "बिल्ली"], अक्षर =[ए, जी, ओ, ओ, डी, डी, डी, सी, टी, टी] और स्कोर =[5,0,8,3,0,0,0,6,0,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0, 0,0,0], तो आउटपुट 30 होगा, यहाँ अच्छा है और कैट अधिकतम स्कोर बना रहे हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक 2डी सरणी डीपी परिभाषित करें
-
एक फ़ंक्शन कैल्क () को परिभाषित करें, इसमें s, एक मैप m, एक सरणी sc,
लगेगा -
उत्तर:=0
-
इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -
-
एक्स:=एस [i]
-
अगर m[x] <=0, तो -
-
वापसी 0
-
-
(m[x] 1 से घटाएं)
-
उत्तर:=उत्तर + एससी [एक्स - 'ए']
-
-
वापसी उत्तर
-
फ़ंक्शन को हल करें () को परिभाषित करें, यह i, स्थिति, जोड़े की एक सरणी v, एक नक्शा m, एक सरणी s,
लेगा। -
अगर मैं -1 के समान हूं, तो -
-
वापसी 0
-
-
x :=.v[i] का दूसरा मान
-
उत्तर:=0
-
अगर स्थिति 1 के समान है, तो -
-
उत्तर:=कैल्क (एक्स, एम, एस)
-
-
अगर उत्तर> 0 और स्थिति 1 के समान है, तो -
-
इनिशियलाइज़ j :=0 के लिए, जब j
-
(m[x[j]] 1 से घटाएं)
-
-
-
उत्तर + अधिकतम हल करें (i - 1, 0, v, m, s) और हल करें (i - 1, 1, v, m, s)
-
मुख्य विधि से, निम्न कार्य करें -
-
उत्तर:=0
-
एक नक्शा परिभाषित करें मी
-
इनिशियलाइज़ i :=0 के लिए, जब i <का आकार l, अपडेट (i से 1 तक बढ़ाएँ), करें -
-
(m[l[i]] 1 से बढ़ाएं)
-
-
जोड़े की एक सरणी v परिभाषित करें
-
प्रारंभ करने के लिए i:=0, जब i
-
एक्स:=डब्ल्यू[i]
-
झंडा:=कैल्क (एक्स, एम, एस)
-
अगर झंडा गैर-शून्य है, तो -
-
v
. के अंत में {ध्वज, x} डालें
-
-
-
सरणी को क्रमबद्ध करें v
dp :=आकार की एक 2D सरणी (v का आकार) x 2 परिभाषित करें और इसे -1 से भरें
हल की अधिकतम वापसी (v, 0, v, m, s का आकार) और हल करें (v, 1, v, m, s का आकार)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int> > dp;
int calc(string s, map<char, int> m, vector<int>& sc){
int ans = 0;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
if (m[x] <= 0)
return 0;
m[x]--;
ans += sc[x - 'a'];
}
return ans;
}
int solve(int i, int status, vector<pair<int, string> > v,
map<char, int> m, vector<int>& s){
if (i == -1)
return 0;
string x = v[i].second;
int ans = 0;
if (status == 1)
ans = calc(x, m, s);
if (ans > 0 && status == 1) {
for (int j = 0; j < x.size(); j++) {
m[x[j]]--;
}
}
return ans + max(solve(i - 1, 0, v, m, s), solve(i - 1, 1, v, m, s));
}
int maxScoreWords(vector<string>& w, vector<char>& l,
vector<int>& s){
int ans = 0;
map<char, int> m;
for (int i = 0; i < l.size(); i++)
m[l[i]]++;
vector<pair<int, string> > v;
for (int i = 0; i < w.size(); i++) {
string x = w[i];
int flag = calc(x, m, s);
if (flag) {
v.push_back({ flag, x });
}
}
sort(v.begin(), v.end());
dp = vector<vector<int> >(v.size(), vector<int>(2, -1));
return max(solve(v.size() - 1, 0, v, m, s), solve(v.size() -
1, 1, v, m, s));
}
};
main(){
Solution ob;
vector<string> words = {"god", "good", "toc", "cat"};
vector<char> letters = {'a','g','o','o','d','d','d','c','t','t'};
vector<int> score = {5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0};
cout << (ob.maxScoreWords(words, letters, score));
} इनपुट
{"god", "good", "toc", "cat"},
{'a','g','o','o','d','d','d','c','t','t'},
{5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0} आउटपुट
30
