C ++中的奇怪打印机

  • Z时代
  • 2024-01-10
  • 分类：综合

假设有一台奇怪的打印机，它有一些要求-

  • 打印机每次只能打印相同字符的序列。

  • 在每一回合中，打印机都可以打印从任何地方开始和在任何地方结束的新字符，并且将覆盖原来的现有字符。

因此，如果我们的字符串由小写字母组成，则我们的任务是计算打印机打印所需的最少转数。

因此，如果输入类似“ aaabba”，则将花费2圈，首先打印aaaaa，然后通过替换字符打印b。

为了解决这个问题，我们将遵循以下步骤-

  • n：= s的大小

  • 如果n与0相同，则：返回0

  • 定义一个nxn阶的2D数组dp，并用无穷大填充

  • 对于初始化l：= 1，当l <= n时，更新（将l增加1），-

    • 对于初始化k：= i，当k <j时，更新（k增加1），做-

    • temp：= dp [i，k] + dp [k + 1，j]

    • dp [i，j]：= dp [i，j]的最小值，并且（当s [k]与s [j]相同时为temp – 1，否则为temp。

    • dp [i，j]：= 1，当s [i]与s [j]相同时，否则为2

    • 如果l与1相同，则：dp [i，j]：= 1

    • 对于初始化i：= 0，j：= l-1，当j <n时，更新（i增加1），（j增加1），-

    • 否则，当l与2相同时，则-

    • 除此以外

    • 返回dp [0，n-1]

    让我们看下面的实现以更好地理解-

    示例

    #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

    以上是 C ++中的奇怪打印机 的全部内容， 来源链接： utcz.com/z/316550.html

    回到顶部