C++에서 문자로 구성된 최대 점수 단어

<시간/>

단어 목록, 단일 문자 목록 및 모든 문자에 대한 점수가 있다고 가정합니다. 주어진 문자를 사용하여 형성된 유효한 단어 집합의 최대 점수를 찾아야 합니다.

문자의 모든 문자를 사용할 수 없으며 각 문자는 한 번만 사용할 수 있습니다. '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}