C++での最適な除算

正の整数のリストがあるとします。隣接する整数は浮動小数点除算を実行します。たとえば、[2,3,4]-> 2/3/4です。これで、任意の位置に任意の数の括弧を追加して、これらの操作の優先度を変更できます。最大の結果を得るには、括弧を追加する方法を見つける必要があります。対応する式を文字列形式で見つける必要があります。式に冗長な括弧を含めることはできません。したがって、入力が[1000,100,10,2]の場合、結果は「1000 /（100/10/2）」になります。

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

• n：=nums配列のサイズ
• nが0の場合、空白の文字列を返します。
• num：=nums [0] as string
• nが1の場合、numを返します
• nが2の場合、num concatenate /を返し、nums[1]を文字列として連結します
• den：=空の文字列
• 1からn–1の範囲のiの場合
  • den：=den + nums [i] as string
  • iがn– 1でない場合、den：=den concatenate‘/’
• return num concatenate / concatenate（concatenate den、concatenate）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string optimalDivision(vector<int>& nums) {
      int n = nums.size();
      if(n == 0) return "";
      string num = to_string(nums[0]);
      if(n == 1) return num;
      if(n == 2) return num + "/" + to_string(nums[1]);
      string den = "";
      for(int i = 1; i < n; i++){
         den += to_string(nums[i]);
         if(i != n - 1) den += "/";
      }
      return num + "/" + "(" + den + ")";
   }
};
main(){
   vector<int> v = {1000,100,10,2};
   Solution ob;
   cout << (ob.optimalDivision(v));
}

入力

[1000,100,10,2]

出力

1000/(100/10/2)