คำคะแนนสูงสุดที่เกิดขึ้นจากตัวอักษรใน C ++

สมมติว่าเรามีรายการคำ รายการตัวอักษรเดี่ยว และคะแนนสำหรับอักขระทุกตัว เราต้องหาคะแนนสูงสุดของชุดคำที่ถูกต้องที่สร้างขึ้นโดยใช้ตัวอักษรที่กำหนด

เราไม่สามารถใช้ตัวอักษรทั้งหมดในตัวอักษรและแต่ละตัวอักษรสามารถใช้ได้เพียงครั้งเดียว คะแนนของตัวอักษร 'a', 'b', 'c', ... ,'z' กำหนดโดย score[0], score[1], ... , score[25] ตามลำดับ

ดังนั้น หากการป้อนข้อมูลเป็นเหมือนคำ =["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,2,0,0,0,0, 0,0,0] จากนั้นผลลัพธ์จะเป็น 30 ที่นี่ดีและแมวทำคะแนนสูงสุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ 2 มิติหนึ่ง dp

• กำหนดฟังก์ชัน calc() ซึ่งจะใช้เวลา s หนึ่งแผนที่ m อาร์เรย์ sc

• ตอบ :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=s[i]

  • ถ้า m[x] <=0 แล้ว −

    • คืนค่า 0

  • (ลด m[x] ลง 1)

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

• กลับมาอีกครั้ง

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ i, สถานะ, อาร์เรย์ของคู่ v, หนึ่งแผนที่ m, อาร์เรย์ s,

• ถ้าฉันเหมือนกับ -1 แล้ว −

  • คืนค่า 0

• x :=.second ค่าของ v[i]

• ตอบ :=0

• หากสถานะเหมือนกับ 1 แล้ว −

  • ตอบ :=calc(x, m, s)

• ถ้า ans> 0 และสถานะเหมือนกับ 1 แล้ว −

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • (ลด m[x[j]] ลง 1)

• คืนค่า ans + ค่าสูงสุดของการแก้ปัญหา (i - 1, 0, v, m, s) และแก้ปัญหา (i - 1, 1, v, m, s)

• จากวิธีหลัก ให้ทำดังนี้ −

• ตอบ :=0

• กำหนดหนึ่งแผนที่ m

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • (เพิ่ม m[l[i]] โดย 1)

• กำหนดอาร์เรย์ v ของคู่

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=w[i]

  • ธง :=calc(x, m, s)

  • ถ้าแฟล็กไม่ใช่ศูนย์ ดังนั้น −

    • แทรก { flag, x } ที่ส่วนท้ายของ v

• จัดเรียงอาร์เรย์ v

  dp :=กำหนดขนาดอาร์เรย์ 2 มิติ (ขนาด 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