단어 목록, 단일 문자 목록 및 모든 문자에 대한 점수가 있다고 가정합니다. 주어진 문자를 사용하여 형성된 유효한 단어 집합의 최대 점수를 찾아야 합니다.
문자의 모든 문자를 사용할 수 없으며 각 문자는 한 번만 사용할 수 있습니다. 'a', 'b', 'c', ... ,'z' 문자의 점수는 각각 score[0], score[1], ... , score[25]로 지정됩니다.
따라서 입력이 단어 =["신", "좋은", "toc", "고양이"]와 같으면 문자 =[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이 됩니다. 여기에서는 양호하고 고양이는 최대 점수를 기록하고 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 2D 배열 dp 정의
-
calc() 함수를 정의하면 s, 하나의 맵 m, 배열 sc,
-
답변 :=0
-
initialize i :=0의 경우 i
-
x :=s[i]
-
m[x] <=0이면 -
-
0 반환
-
-
(m[x]를 1만큼 감소)
-
ans :=ans + sc[x - 'a']
-
-
반환
-
solve() 함수를 정의합니다. 이것은 i, status, 쌍 v의 배열, 하나의 맵 m, 배열 s,
를 취합니다. -
i가 -1과 같으면 -
-
0 반환
-
-
x :=v[i]의 두 번째 값
-
답변 :=0
-
상태가 1과 같으면 -
-
ans :=계산(x, m, s)
-
-
ans> 0이고 상태가 1과 같으면 -
-
j 초기화의 경우:=0, j
-
(m[x[j]] 1만큼 감소)
-
-
-
solve(i - 1, 0, v, m, s) 및 solve(i - 1, 1, v, m, s)의 ans + 최대값 반환
-
기본 방법에서 다음을 수행하십시오 -
-
답변 :=0
-
하나의 맵 정의
-
initialize i :=0의 경우, i
-
(m[l[i]] 1씩 증가)
-
-
쌍의 배열 v 정의
-
initialize i :=0의 경우, i
-
x :=w[i]
-
플래그 :=계산(x, m, s)
-
플래그가 0이 아닌 경우 -
-
v
끝에 { flag, x } 삽입
-
-
-
배열 v
정렬dp :=크기(v의 크기) x 2인 하나의 2D 배열을 정의하고 -1로 채웁니다.
solve(v, 0, v, m, s의 크기) 및 solve(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