NCPC 2002
http://www.ida.liu.se/projects/progcontest/progsm/2002/
- A
예전 예선 금고 문제와 유사한데, 조금더 생각해줘야 함.
우선 높이가 1일때, 금고가 1개 있을때는 다 구해준다.
d[k][m][t] 는 i번째 터트렸을때 터지면 밑을, 안터지면 위를 생각하면 되므로 아래와 같다. 그러나 위를 구할때는 최초 1개가 아닌 i+1개를 터트려야 하므로 t라는 변수를 추가했다.
d[k][m][t] = min(i = 2 ~m-1)( t + i + max(d[k-1][i-1][t], d[k][m-i][t+i])이다. (여기서 t는 밑에 t개를 놓았을때의 경우이다. t+i는 최대 쿠키의 개수보다 작거나 같아야 한다)
t는 내림으로, k와 m은 오름으로 구하면 된다.
실수: 2개중 큰것은데 처음에 더한걸로 구했다..ㅡㅜ
- E
다해봤다. 브랜치엔 바운드로 이걸로 하면 안되겠다. 중복만 제거해도 상당히 효과가 있다.
E.cpp
