Máy in lạ trong C ++

Giả sử có một máy in lạ Nó có một số yêu cầu -

Máy in chỉ có thể in một dãy ký tự giống nhau mỗi lần.
Trong mỗi lượt, máy in có thể in các ký tự mới bắt đầu và kết thúc ở bất kỳ vị trí nào và sẽ bao gồm các ký tự hiện có ban đầu.

Vì vậy, nếu chúng ta có một chuỗi bao gồm các chữ cái thường, nhiệm vụ của chúng ta là đếm số lượt tối thiểu mà máy in cần để in nó.

Vì vậy, nếu đầu vào giống như “aaabba”, thì nó sẽ mất 2 lượt, đầu tiên in aaaaa sau đó là b bằng cách thay thế các ký tự.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước của s
nếu n giống 0, thì:trả về 0
Xác định một dp mảng 2D có thứ tự n x n, điền vào vô cực
để khởi tạo l:=1, khi l <=n, cập nhật (tăng l lên 1), thực hiện -
- để khởi tạo i:=0, j:=l - 1, khi j
- nếu l giống 1 thì:dp [i, j]:=1
ngược lại khi l giống 2 thì -
- dp [i, j]:=1 khi s [i] giống s [j] nếu không thì 2
Mặt khác
- để khởi tạo k:=i, khi k
- temp:=dp [i, k] + dp [k + 1, j]
- dp [i, j]:=tối thiểu là dp [i, j] và (temp-1 khi s [k] giống s [j] nếu không thì temp.

trả về dp [0, n - 1]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

“2*”

Máy in lạ trong C ++

Ví dụ

Đầu vào

Đầu ra