[UVA 307]Sticks(DFS 역 추적+가지치기)

Sticks
제목 링크:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=17446
제목 의 대의:
n 개의 작은 나무 막대 가 있 습 니 다.길이 가 다 릅 니 다.지금 은 길이 가 같은 나무 막대 로 만들어 달라 고 합 니 다.몇 길이 의 나무 막대 로 만 들 었 는 지 물 어보 면 가장 많은 나무 막대 수 를 얻 을 수 있 습 니 다.
예 를 들 면:
출력
문제 풀이 방향:
이 문 제 는 DFS 의 역 추적 을 쉽게 생각 할 수 있다.관건 은 가 지 를 자 르 는 데 다음 과 같은 몇 개의 가지치기 가 있다 는 것 이다.1.모든 나무 막대 의 길 이 를 큰 것 에서 작은 것 으로 배열 하고 나무 막대 기 를 조합 할 때 긴 나무 막대 기 를 우선 사용 하면 조합 속 도 를 가속 화하 고 뒤의 가지치기 에 도움 이 된다.2.나무 막대기 의 길 이 는 반드시 가장 긴 나무 막대기 와 같은 길이 보다 크 고 모든 나무 막대기 의 길이 와 작은 것 임 을 증명 하기 쉽다.3.나무 막대기 의 길 이 는 반드시 모든 나무 막대기 의 길이 와 약 수 를 나타 내 는데 이것 도 쉽게 증명 할 수 있다.4.어떤 나무 막대 의 조합 과정 에서 현재 의 나무 막대 stick[i]에 대해 stick[i-1]이 조합 되 지 않 고 stick[i]==stick[i-1]이 라면 stick[i]를 고려 할 필요 가 없다.이미 stick[i-1]을 시 도 했 는데 조합 이 안 되 는 것 을 발 견 했 기 때문에 stick[i]는 더욱 안 될 것 이다.5.만약 에 이번에 i 번 째 나무 막대 기 를 시도 하 는 첫 번 째 부분 이 라면 stick[j]가 현재 사용 할 수 있 는 가장 긴 나무 막대 라 고 가정 하고 이번 조합 이 실패 하면 검색 을 종료 하고 i-1 번 나무 막대 에 대한 검색 으로 되 돌아 갑 니 다.스틱[j]이 i 번 나무 막대기 의 첫 번 째 부분 으로 조합 할 수 없 으 면 i+k(k>0)의 나무 막대기 의 첫 번 째 부분 으로 도 안 되 기 때문이다.이때 남 은 나무 막대 가 더 적 고 부분 집합 이기 때문이다.6.한 토막 으로 나무 막대 기 를 완성 할 수 있다 면 여러 단락 으로 조합 할 필요 가 없다.한 단락 으로 한 단락 을 대체 할 수 있 지만 한 단락 으로 여러 단락 을 대체 할 수 없 기 때문이다.
이 제목 의 가지치기 가 매우 고전적 이어서 좋 은 제목 이다.

9
5 2 1 5 2 1 5 2 1