생각날때마다 올리는 블로그

문제 링크https://www.acmicpc.net/problem/5475https://oj.uz/problem/view/IOI07_miners 문제 요약광부들은 자신이 최근에 먹은 세 끼의 종류에 따라 캐는 석탄의 양이 달라진다. 다 다를 경우 3, 두 종류 일 경우 2, 한 종류 일 경우 1이다.들어오는 식사의 개수의 종류는 3개이고, 광산은 총 2개 있다. 식사가 들어가지 않으면 0개의 석탄이 생산된다. 광부들이 최대로 생산해낼 수 있는 석탄의 양을 구하여라. dp 배열들의 정의와 그것을 통한 아이디어 끌어오기cost[i][j][k]=음식의 순서가 차례대로 i,j,k로 들어왔을 때 얻을 수 있는 석탄의 양비어 있는 경우는 3으로 정의한다.비어 있는 경우는 맨 처음 생기게 된다. 아무것도 없는 상황에..

문제 링크https://www.acmicpc.net/problem/5466https://oj.uz/problem/view/IOI09_salesman 문제 요약상인이 어떤 마을의 시장에서 다른 마을의 시장으로 가서 이득을 취할려고 한다.위로 올라갈 때에는 U의 비용이, 아래로 내려갈 때에는 D의 비용이 들고, 각 마을의 위치는 $P_i$,각 마을에서 얻을 수 있는 이득은 $M_i$이다.각 마을의 시장이 열리는 날은 $D_i$이며, 마지막에 방문한 곳에서 집으로 꼭 와야한다. 집의 좌표는 S이다.이 때, 상인이 얻을 수 있는 최대 이득은 얼마인가? 간단한 DP( Subtask 1, $N\leq5000$ )dp[i] : i번째시장까지 얻을 수 있는 상인의 최대 이득최초엔 상인은 집의 위치에 있고, 마지막엔 항..

icpc.me/5465https://oj.uz/problem/view/IOI09_mecho문제 요약1초마다 현재 별들이 있는 위치에서 별들이 사방으로 퍼진다고 한다. 곰돌이는 현재 위치에서 최대한 많이 꿀을 빨아먹고 벌에 물리지 않고 집을 가고 싶어한다.과연, 얼마나 많은 꿀을 빨아먹을 수 있을것인가? 단, 곰돌이는 1초에 S번 움직일 수 있고, 곰돌이는 현재 위치에서 상하좌우로 이동할 수 있다. 관찰만약, T일 동안 꿀을 빨고, 출발해도 충분히 집에 도달할 수 있다고 하자. 그럼, T-n ( 0 < n = pre[sx][sy]) return false; queue q; q.push(make_pair(make_pair(sx,sy),time*s)); reach[sx][sy]=1; while(!q.empty..