백준14869 요리 강좌

작성일 | In

문제 링크

  • http://icpc.me/14869

문제 출처

  • 2017 KOI 고등부 3번

사용 알고리즘

  • DP
  • Sliding Window

시간복잡도

  • $O(NM)$

풀이

$DP(i, j)$를 i번째 강좌까지 수강했고, 마지막으로 수강한 학원이 j이면서 학원을 옮기려는 할 때의 최소 비용으로 정의를 하고 문제를 풉시다.

$C(a, b)$를 a학원의 첫 번째 강좌부터 b번째 강좌까지 수강한 비용이라고 정의하면, $DP(i, j) = min(DP(u, v) + T + C(j, i) - C(j, u))$입니다. (단, $S ≤ i-u ≤ E, v ≠ j, v ≠ B[j]$)

위 점화식에서 u, v와 관련된 항과 관련되지 않은 항으로 나누어서 보면, 모든 v에 대해 $DP(u, v) - C(j, u)$의 최솟값을 구해서 $T + C(j, i)$를 더해주면 됩니다.

v의 조건이 $v ≠ j, v ≠ B[j]$ 총 2가지이므로, $DP(u, v) $의 가장 작은 3개만 구해놓으면 그중 하나는 무조건 정답이 됩니다.
또한 $[i-E, i-S]$구간은 i가 증가함에 따라 항상 오른쪽으로 이동하므로 N개의 deque를 만들어서 각 u에 대해 $DP(u, v)$ 의 가장 작은 3개를 deque를 이용해 sliding window 느낌으로 관리하면 된다는 것을 알 수 있습니다.

$O(NM)$에 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int x, v;
	//dq : day, cost
	//mn : academy, cost
};

Node mn[3030][3]; //3개까지만 들고 있으면 됨
deque<Node> dq[3030];

const int inf = 1e9+7;

int n, m, s, e, t;
int a[3030][3030];
int b[3030];
int dp[3030][3030], sum[3030][3030];

int f(int day, int x){
	if(mn[day][0].x != x && mn[day][0].x != b[x]) return mn[day][0].v;
	if(mn[day][1].x != x && mn[day][1].x != b[x]) return mn[day][1].v;
	return mn[day][2].v;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> s >> e >> t;
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
		cin >> a[i][j];
		sum[i][j] = sum[i][j-1] + a[i][j];
	}
	for(int i=1; i<=n; i++) cin >> b[i];

	for(int i=1; i<=m; i++){
		for(int j=1; j<=n; j++){
			if(i >= s){
				int now = f(i-s, j) - sum[j][i-s];
				while(dq[j].size() && dq[j].back().v >= now) dq[j].pop_back();
				dq[j].push_back({i-s, now});
			}
			while(dq[j].size() && dq[j].front().x < i-e) dq[j].pop_front();
			if(dq[j].empty() || dq[j].front().v >= 1e9) dp[i][j] = inf;
			else dp[i][j] = dq[j].front().v + t + sum[j][i];
		}
		for(int j=0; j<3; j++) mn[i][j] = {0, inf};
		for(int j=1; j<=n; j++){
			if(dp[i][j] >= 1e9) continue;
			if(dp[i][j] < mn[i][0].v){
				mn[i][2] = mn[i][1]; mn[i][1] = mn[i][0]; mn[i][0] = {j, dp[i][j]};
			}else if(dp[i][j] < mn[i][1].v){
				mn[i][2] = mn[i][1]; mn[i][1] = {j, dp[i][j]};
			}else{
				mn[i][2] = {j, dp[i][j]};
			}
		}
	}
	int ans = inf;
	for(int i=1; i<=n; i++){
		for(int j=m-e; j<m; j++){
			int now = f(j, i);
			if(now >= 1e9) continue;
			ans = min(ans, now + sum[i][m] - sum[i][j]);
		}
	}
	cout << ans;
}