USACO March 2014 Contest > Silver

 

딱히 재미도 감동도 없는 셋이였다... 

---

 

10021: Watering the Fields (G3, mst)

 

MST 기본 문제이다. 필요한 간선만 만들어서 mst로 슥삭해주면 된다.

 

---

 

10022: The Lazy Cow (G4, 누적 합)

 

그나마 재밌었던 문제이다. 어떤 시작점으로부터 맨해튼 거리가 $K$ 이하인 점들의 값 합을 최대화하는 문제인데 제한이 작아서 브루트포스를 돌리면 된다. 맨해튼 거리의 contour는 다이아몬드 모양으로 구현이 불편하기 때문에, 45도 돌려서 체비쇼프 거리 꼴로 변환하여 2차원 정사각형 누적합의 최대를 구해주면 된다. 거리 변환 시 빈 공간이 생기는데, 시작점이 빈 공간이 되지 않도록 잘 확인해줘야 한다.

 

---

 

10023: Mooo Mooo (G4, DP)

 

문제를 잘 변형하면 어떤 정수 $m$에 대해 $V(i)$들을 적절히 더해서 $m$을 만들 수 있는지 판별하는 문제가 된다. 제한이 작으므로 냅색 문제 형태 DP로 충분히 해결할 수 있다.