C: 욕심매번 가장 작은 조건 을 만족 시 키 는 분동 을 선택 하면 된다. 그러면 뒤에 더 많은 선택의 여 지 를 남 길 수 있다. 하지만 그것 만으로 도 작은 문제 가 있 습 니 다.그 때 는 그냥 욕심 내 서 끊 었 는데......................................................... 우 리 는 먼저 첫 번 째 분동 을 열 어 누 구 를 놓 아야 하 는 지 를 열 어 놓 고 욕심 을 부리 기 시작 해 야 한다. 예 를 들 면: 분동 이 있 습 니 다. 1, 2, 3. 4 개 넣 어야 합 니 다. 단순히 욕심 이 많 으 면 이렇게 선택 합 니 다: 1, 2, 3, *.(* 선택 할 수 없 음, 종 료 됨) 왼쪽 천평 은 1 + 3 = 4kg, 오른쪽 은 3kg 이다. 이때 분동 1, 2 를 선택 하면 4, 불법 보다 크 면 안 된다.선택 3, 앞 과 중복, 불법. 하지만 사실 우 리 는 2, 3, 2, 3 을 넣 을 수 있어 요. 풀 수 있어 요. 그래서 첫 번 째 저울추 를 들 고 욕심 을 내야 한다. code:
D: 선분 수. 인접 한 두 개의 수 를 합 치 는 것 은 선분 나무 가 왼쪽 나무 와 오른쪽 나 무 를 합 치 는 것 과 같다. 각 노드 에 저 장 된 것 은 이 구간 이 하나의 수 를 합성 한 후의 값 이다.그리고 이 노드 의 두 개의 키 노드 가 어떤 연산 을 해 야 하 는 지 표시 합 니 다. 매번 값 을 수정 할 때마다 단일 업데이트 입 니 다. 바 이 너 리 한 분 한 분 을 따로 고려 할 수 있 습 니 다.(쓰 고 보 니 바 이 너 리 를 따로 생각 하지 않 고 바로 계산 하면 돼. 졸계 야...) code:
E: 맨 왼쪽 (오른쪽) 의 오 열 위 치 를 찾 을 때마다 이 위치 에 놓 아야 할 수 를 이 위치 로 되 돌려 줍 니 다. 몇 번 후에 반드시 원시 서열 로 돌아 갈 수 있다.그러나 문 제 는 최대 3 회 까지 조작 해 야 하기 때문에 dfs 가 3 회 이하 의 답 을 찾 아야 한다. 복잡 도 에 대해 서 는 이렇게 폭 수 를 하 는데 왜 TLE 를 못 해? 내 졸계 의 분석 아래: 원시 서열 에서 최대 3 을 뒤 집 으 면 가장 왼쪽 (오른쪽) 의 잘못된 배열 위치 가 많 지 않 고 x 개가 있다 고 가정 할 수 있다. 그래서 dfs 의 복잡 도 최 악 O (nx ^ 2 ^ 3). x. 분명히 크 지 않 아 요. 느낌 이 그래 요. 그리고 3 번 이내 의 풀이 가 있 을 수 밖 에 없 기 때문에 몇 번 을 뒤 져 도 정확 한 위치 에 있 는 경우 가 많 을 것 이다. 사실 관건 은 최대 3 번 의 제한 이 복잡 도 를 낮 추고 3 번 이상 은 모두 잘 랐 으 며 3 번 이하 도 많 지 않다 는 것 이다. 이상 의 분석 은 보지 않 는 것 이 좋 습 니 다. 왜냐하면 완전히 제 가 추측 한 것 이기 때 문 입 니 다. 만약 큰 신 이 엄밀 한 분석 을 한다 면, 아래층 에서 약 한 요 리 를 알려 주 기 를 바란다. code: