TopCoder SRM 568 Div1

2013. 01. 30.

아...얼마만에 받아보는 빵점인가!!!

레이팅 떨어지는 소리가 들려온다... 그린이 날 부른다..

여러분

INFINITE 를 (1<<25)처럼 작은 수로 잡는 버릇을 버립시다.

최소 (1<<29)부터 시작해야될거같아요..

아....250.....아오....................걍 다돌리는 쉬운 문젠데.....

왜.....................inf를 1<<25로하는 멍청한짓을...........아.....

250

0, 1, ... , N-1의 번호가 붙어있는 상자가 있고,

이 상자들에 들어있는 빨간공, 파란공, 초록공의 개수가 주어졌을 때,

공을 한 상자에서 한 개씩 꺼내서 다른 한 상자로 옮기는 행위를 최소 몇 번이나 해야

각 상자별로 한 가지 색의 공만 남게 할 수 있는가?

그냥 dp로 3*50^4 를 돌렸다.

그래도 경우의 수가 2천만 개 아래라서 괜찮은 문제다.

dp[idx][r][g][b] = 최소 이동 횟수

idx번째 상자까지 처리햇을때, 빨간공을 가진 상자가 r개 남았을 때, 초록공을 가진 상자가 g개 남았을 때, ...

이렇게 보면 식이 금방 세워진다.

500

1000