C++의 마지막 돌 무게 II

<시간/>

암석 컬렉션이 있다고 가정하고 이제 각 암석에는 양의 정수 가중치가 있습니다. 각 턴에서 우리는 두 개의 돌을 선택하고 함께 부수십시오. 돌에 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]
요청 :=총계 / 2
req + 1 크기의 배열 dp를 만들고 이를 거짓 값으로 채웁니다.
dp[0] :=참, 도달범위 :=0
0 ~ n – 1 범위의 i에 대해
- j의 경우 :=req, j – 스톤[i]>=0일 때 j를 1만큼 감소
  - dp[j] :=(dp[j] 및 dp[j –stones[i]]) 둘 다 거짓이면 거짓, 그렇지 않으면 참
  - dp[j]가 참이면 도달 범위:=도달 범위의 최대값 및 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]