C++の文字によって形成される最大スコアの単語

単語のリスト、1文字のリスト、およびすべての文字のスコアがあるとします。与えられた文字を使用して形成された有効な単語セットの最大スコアを見つける必要があります。

文字にすべての文字を使用できるわけではなく、各文字は1回しか使用できません。文字のスコア'a'、'b'、'c'、...、'z'は、それぞれscore [0]、score [1]、...、score[25]で与えられます。

したがって、入力がwords =["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になります。ここでは、良好で猫が最大スコアを獲得しています。

これを解決するには、次の手順に従います-

• 1つの2D配列dpを定義します

• 関数calc（）を定義します。これには、s、1つのマップm、配列sc、

  が必要です。

• ans：=0

• 初期化i：=0の場合、i

  • x：=s [i]

  • m [x] <=0の場合、-

    • 0を返す

  • （m [x]を1減らします）

  • ans：=ans + sc [x-'a']

• ansを返す

• 関数solve（）を定義します。これには、i、ステータス、ペアの配列v、1つのマップm、配列s、

  が必要です。

• iが-1と同じ場合、-

  • 0を返す

• x：=.v [i]

  の2番目の値

• ans：=0

• ステータスが1と同じ場合、-

  • ans：=calc（x、m、s）

• ans> 0でステータスが1と同じ場合、-

  • 初期化j：=0の場合、j

    • （m [x [j]]を1減らします）

• ans +最大のsolve（i-1、0、v、m、s）とsolve（i-1、1、v、m、s）を返します

• メインの方法から、次のようにします-

• ans：=0

• 1つのマップを定義するm

• 初期化i：=0の場合、i

  • （m [l [i]]を1増やします）

• ペアの配列vを定義する

• 初期化i：=0の場合、i

  • x：=w [i]

  • フラグ：=calc（x、m、s）

  • フラグがゼロ以外の場合、-

    • vの最後に{フラグ、x}を挿入します

• 配列を並べ替えるv

  dp：=サイズ（vのサイズ）x 2の2D配列を1つ定義し、これに-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