백준14870 조개 줍기

작성일 | In

문제 링크

  • http://icpc.me/14870

문제 출처

  • 2017 전국 본선 고등부4

사용 알고리즘

  • DP
  • Fenwick Tree

시간복잡도

  • O(N2logN)

풀이

Subtask 1 (N <= 100, 12pt)

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j]를 이용해 O(N3)애 구할 수 있습니다.

Subtask 3 (100pt)


이런식으로 입력이 주어졌을 때, DP값은 아래와 같습니다.

화살표는 해당 칸의 dp값을 구하는데 사용된 칸을 가리킵니다. 다시 말해, 화살표가 가리키고 있는 칸의 값이 바뀌면 자신의 값도 바뀌게 됩니다.

화살표는 항상 왼쪽 혹은 위를 향합니다. 그러므로 어떤 칸의 값이 바뀌게 되면 아래 혹은 오른쪽의 dp값이 바뀝니다.
계단 형태로 바뀐다고 볼 수 있습니다.

각 행마다 바뀌는 구간은 연속하므로 펜윅 트리나 세그먼트 트리 등의 자료구조로 관리해줄 수 있습니다.
각 쿼리마다 모든 행에 대해 값이 바뀌는 구간을 찾아주고, 각각의 행을 관리하는 자료구조를 이용해 값을 추출/갱신해주면 O(N2logN)에 문제를 풀 수 있습니다.

전체 코드

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;

struct BIT{
	ll tree[1515];

	void update(int l, int r, int v){
		for(; l<=n; l+=l&-l) tree[l] += v;
		for(r++; r<=n; r+=r&-r) tree[r] -= v;
	}

	ll query(int x){
		ll ret = 0;
		for(; x; x^=x&-x) ret += tree[x];
		return ret;
	}
} tree[1515];

int arr[1515][1515];
int dp[1515][1515];
ll ans = 0;
int s[1515], e[1515];

inline ll get(int i, int j){
	return dp[i][j] + tree[i].query(j);
}

void getDP(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j];
			ans += dp[i][j];
		}
	}
}

void query(int a, int b, int c){
	s[a] = e[a] = b;
	for(int i=a+1; i<=n; i++) s[i] = n+1, e[i] = 0;

	for(int i=a, j=b;;){
		if(j < n && max(get(i-1, j+1), get(i, j)) + c == max(get(i-1, j+1), get(i, j) + c)) j++;
		else i++;
		if(i > n) break;
		e[i] = j;
	}
	for(int i=a, j=b;;){
		if(i < n && max(get(i+1, j-1), get(i, j)) + c == max(get(i+1, j-1), get(i, j) + c)) i++;
		else j++;
		if(j > n || e[i] < j) break;
		s[i] = min(s[i], j);
	}

	for(int i=a; i<=n; i++){
		if(s[i] > e[i]) continue;
		tree[i].update(s[i], e[i], c);
		ans += c * (e[i] - s[i] + 1);
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> arr[i][j];
		}
	}
	getDP();
	cout << ans << "\n";

	for(int i=1; i<=n; i++){
		int a, b; char op;
		cin >> op >> a >> b;
		if(op == 'U') query(a, b, 1);
		else query(a, b, -1);
	}
}