[BOJ] 4011 기름 파기

https://www.acmicpc.net/problem/4011

4011번: 기름 파기

구역을 최대 3개만 팔 수 있기 때문에 여러가지 경우를 구상해 볼 수 있다.

세로로 3개 나란히

가로로 3개 나란히

왼쪽 위에 하나, 왼쪽 아래에 하나, 오른쪽에 하나

왼쪽 위에 하나, 오른쪽 위에 하나, 아래에 하나

왼쪽에 하나, 오른쪽 위에 하나, 오른쪽 아래에 하나

위에 하나, 왼쪽 아래에 하나, 오른쪽 아래에 하나

총 6가지 경우가 있다.

왼쪽 위에서 부터 시작하는 DP, 오른쪽 위에서 부터 시작하는 DP, 왼쪽 아래에서 부터 시작하는 DP, 오른쪽 아래에서 부터 시작하는 DP테이블을 만든다.

DP테이블의 정의는 \(dp[i][j]\) : 시작점부터 \((i,j\))까지 의 영역에서 기름을 파낼 한 구간을 구할 때 최대 이익.

 

방금 내가 말한 모든 케이스를 처리해보면, 우리가 구하고자 하는 답이 나오고, AC를 받을 수 있다.

시간복잡도는 \(O(N^{2}M^{2})\) 이다,

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
int a[1505][1505];
int d[5][1505][1505];
int s[5][1505][1505];
int dn[1505][1505],dm[1505][1505];
int maxN[1505];
int maxM[1505];
int dx[5] = {0,-1,-1,1,1},dy[5] = {0,-1,1,-1,1};

int sum(int x1,int y1,int x2,int y2,int wh) { 
	return s[wh][x1][y1]-s[wh][x2+dx[wh]][y1]-s[wh][x1][y2+dy[wh]]+s[wh][x2+dx[wh]][y2+dy[wh]];
}

void initSum() {
	for(int i = 1;i <= n;i++) 
		for(int j = 1;j <= m;j++) 
			s[1][i][j] = s[1][i-1][j]+s[1][i][j-1]-s[1][i-1][j-1]+a[i][j];
	for(int i = 1;i <= n;i++) 
		for(int j = m;j >= 1;j--) 
			s[2][i][j] = s[2][i-1][j]+s[2][i][j+1]-s[2][i-1][j+1]+a[i][j];
	for(int i = n;i >= 1;i--) 
		for(int j = 1;j <= m;j++) 
			s[3][i][j] = s[3][i+1][j]+s[3][i][j-1]-s[3][i+1][j-1]+a[i][j];
	for(int i = n;i >= 1;i--) 
		for(int j = m;j >= 1;j--) 
			s[4][i][j] = s[4][i+1][j]+s[4][i][j+1]-s[4][i+1][j+1]+a[i][j];
}

void initDynamic() {
	for(int i = k;i <= n;i++) 
		for(int j = k;j <= m;j++) 
			d[1][i][j] = max({d[1][i-1][j],d[1][i][j-1],sum(i,j,i-k+1,j-k+1,1)});
	for(int i = k;i <= n;i++) 
		for(int j = m-k+1;j >= 1;j--) 
			d[2][i][j] = max({d[2][i-1][j],d[2][i][j+1],sum(i,j,i-k+1,j+k-1,2)});
	for(int i = n-k+1;i >= 1;i--) 
		for(int j = k;j <= m;j++) 
			d[3][i][j] = max({d[3][i+1][j],d[3][i][j-1],sum(i,j,i+k-1,j-k+1,3)});
	for(int i = n-k+1;i >= 1;i--) 
		for(int j = m-k+1;j >= 1;j--) 
			d[4][i][j] = max({d[4][i+1][j],d[4][i][j+1],sum(i,j,i+k-1,j+k-1,4)});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) cin >> a[i][j];
	}
	initSum();
	initDynamic();
	int ans = 0;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			ans = max(ans,d[1][i][j]+d[2][i][j+1]+d[3][i+1][m]);
			ans = max(ans,d[1][n][j-1]+d[2][i][j]+d[4][i+1][j]);
			ans = max(ans,d[1][i-1][m]+d[3][i][j]+d[4][i][j+1]);
			ans = max(ans,d[1][i][j]+d[3][i+1][j]+d[2][n][j+1]);
		}
	}
	for(int i = k;i <= n;i++) {
		for(int j = k;j <= m;j++) {
			maxN[i] = max(maxN[i],sum(i,j,i-k+1,j-k+1,1));
			maxM[j] = max(maxM[j],sum(i,j,i-k+1,j-k+1,1));
		}
	}
	for(int i = k;i <= n;i++) {
		for(int j = i+k;j <= n;j++) {
			dn[i][j] = max(dn[i][j-1],maxN[j]);
		}
	}
	for(int i = k;i <= m;i++) {
		for(int j = i+k;j <= m;j++) {
			dm[i][j] = max(dm[i][j-1],maxM[j]);
		}
	}
	for(int i = k;i <= m;i++) {
		for(int j = i+k;j <= m-k;j++) {
			ans = max(ans,d[1][n][i]+dm[i][j]+d[2][n][j+1]);
		}
	}
	for(int i = k;i <= n;i++) {
		for(int j = i+k;j <= n-k;j++) {
			ans = max(ans,d[1][i][m]+dn[i][j]+d[3][j+1][m]);
		}
	}
	cout << ans;
}