เครื่องพิมพ์แปลก ๆ ใน C++

สมมติว่ามีเครื่องพิมพ์แปลก ๆ มันมีข้อกำหนดบางอย่าง -

• เครื่องพิมพ์สามารถพิมพ์ได้เฉพาะลำดับของอักขระเดียวกันในแต่ละครั้ง
• ในแต่ละรอบ เครื่องพิมพ์สามารถพิมพ์อักขระใหม่ที่เริ่มต้นและสิ้นสุดที่ใดก็ได้ และจะครอบคลุมอักขระเดิมที่มีอยู่

ดังนั้นถ้าเรามีสตริงที่ประกอบด้วยอักษรตัวล่าง งานของเราคือนับจำนวนรอบขั้นต่ำที่เครื่องพิมพ์ที่จำเป็นสำหรับการพิมพ์

ดังนั้นหากอินพุตเป็น "aaabba" จะใช้เวลา 2 รอบ พิมพ์ aaaaa ก่อนแล้วจึง b's โดยแทนที่อักขระ

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

• n :=ขนาดของ s
• ถ้า n เหมือนกับ 0 ให้คืนค่า 0
• กำหนดอาร์เรย์ 2 มิติ dp หนึ่งรายการของคำสั่ง n x n เติมค่านี้ด้วยค่าอนันต์
• สำหรับการเริ่มต้น l :=1 เมื่อ l <=n อัปเดต (เพิ่ม l ขึ้น 1) ทำ −
  • สำหรับการเริ่มต้น i :=0, j :=l - 1, เมื่อ j
  • ถ้า l เหมือนกับ 1 แล้ว:dp[i, j] :=1
• มิฉะนั้น เมื่อ l เท่ากับ 2 แล้ว −
  • dp[i, j] :=1 เมื่อ s[i] เหมือนกับ s[j] มิฉะนั้น 2
• มิฉะนั้น
  • สำหรับการเริ่มต้น k :=i เมื่อ k
  • อุณหภูมิ :=dp[i, k] + dp[k + 1, j]
  • dp[i, j] :=ขั้นต่ำของ dp[i, j] และ (temp – 1 เมื่อ s[k] เหมือนกับ s[j] มิฉะนั้น temp

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
   int strangePrinter(string s) {
      int n = s.size();
      if(n == 0) return 0;
      vector < vector <int> > dp(n, vector <int>(n, INF));
      for(int l = 1; l <= n; l++){
      for(int i = 0, j = l - 1; j < n; i++, j++){
         if(l == 1){
            dp[i][j] = 1;
            }else if(l == 2){
               dp[i][j] = s[i] == s[j] ? 1 : 2;
            }else{
               for(int k = i; k < j; k++){
                  int temp = dp[i][k] + dp[k + 1][j];
                  dp[i][j] = min(dp[i][j], s[k] == s[j] ? temp - 1: temp);
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.strangePrinter("aaabba"));
}

อินพุต

“2*”

ผลลัพธ์

2