7개의 댓글이 있습니다.
-
-
Being -
일단 각 사람마다 먹어야 하는 시간이 구간이고, 각 구간에 두 개 이상의 슬롯을 선택하되 한 단위 시간에 선택해야 하는 게 일정 개수 이하여야 하겠네요.
그럼 우리가 어떤 시간에 스테이크 s개를 굽는다면 이건 어떤 손님들한테 할당해야 할까요? 데드라인이 얼마 남지 않은 손님부터 차례로 줘야 하겠지요.
즉 어떤 순간의 상태는 어느 손님까지 스테이크 두 개를 줬고, 어느 손님까지 한 개를 줬는지로 표현되겠네요. 그리고 매 순간 스테이크는 버리는 한이 있더라도 무조건 최대한 구우면 되니, 선택은 굽느냐, 굽지 않느냐 뿐이지요.
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
yeonzzg
문제 링크:
http://acm.timus.ru/problem.aspx?space=1&num=1895
설명:
n(<=50)명의 사람한테 스테이크를 먹여야합니다. 스테이크 마다 1초씩 두번에 걸쳐 구어야합니다. 구울때마다 프라이팬을 쓰는데, 프라이팬의 최소 사용 횟수를 구하는 문제입니다.
제한1: 프라이팬엔 최대 k(<=50)개의 스테키를 올릴수있음.
제한2: i번째 사람이 t[i]에 먹을 때, 두번 구우는 시간 a,b는
(t[i]-x <= a,b < t[i]), (a != b) 이어야 함.
k,x,t[] 모두 입력으로 주어지며, x<=1000,t[i]<=1000입니다.
처음에 그리디한 풀이 + flow 모델을 이용해서 aug path를 하나씩 흘려보며 구하려 했는데 알고리즘이 완전히 틀린것 같습니다 ㅠㅠ
정해는 dp로 최적화라는데... 아무리 생각해도 제겐dp로는 시간복잡도 최적화가 불가능해보이네요..ㅠㅠ 어떻게 해야할까요..
11년 전