C++での最後の石の重みII

岩のコレクションがあり、各岩の重みが正の整数であるとします。各ターンで、2つの岩を選び、それらを一緒に粉砕します。石の重みがxとyで、x<=yの場合。このスマッシュの結果は-

• x =yの場合、両方の石が完全に破壊されます。

• x！=yの場合、重さxの石は完全に破壊され、重さyの石は新しい重さy-xになります。

最後に、残っている石は多くても1つです。この石の可能な限り最小の重量を見つける必要があります（石が残っていない場合、重量は0です）。

たとえば、入力が[2,7,4,1,8,1]の場合、出力は1になります。これは、（2,4）をスマッシュすると、新しい配列が[2 、7,1,8,1]、それらはスマッシュ（7,8）、新しい配列は[2,1,1,1]になり、次にスマッシュ（2,1）、配列は[1,1、 1]、その後スマッシュ（1,1）なので、1つだけが存在します。

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

• n：=石の配列のサイズ、合計を設定：=0

• 0からn–1の範囲のiの場合

  • 合計：=合計+石[i]

• req：=合計/ 2

• サイズreq+1の配列dpを作成し、これをfalse値で埋めます

• dp [0]：=true、到達：=0

• 0からn–1の範囲のiの場合

  • j：=reqの場合、j – stones [i]> =0の場合、jを1減らします

    • dp [j]：=false（dp[j]とdp[j – stones [i]]）の両方がfalseの場合、それ以外の場合はtrue

    • dp [j]がtrueの場合、リーチ：=リーチの最大値とj

• 合計を返す–（2 *リーチ）

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int lastStoneWeightII(vector<int>& stones) {
      int n = stones.size();
      int total = 0;
      for(int i = 0; i < n; i++){
         total += stones[i];
      }
      int req = total / 2;
      vector <bool> dp(req + 1, false);
      dp[0] = true;
      int reach = 0;
      for(int i = 0; i < n; i++){
         for(int j = req; j - stones[i] >= 0; j--){
            dp[j] = dp[j] || dp[j - stones[i]];
            if(dp[j]) reach = max(reach, j);
         }
      }
      return total - (2 * reach);
   }
};
main(){
   vector<int> v = {2,7,4,1,8,1};
   Solution ob;
   cout << (ob.lastStoneWeightII(v));
}

入力

[2,7,4,1,8,1]

出力

1