vva 1427 - Parade(dp+ 단일 큐)

제목 링크: uva 1427 - Parade
제목의 뜻: F성은 n+1 각 가로와 m+1 개의 세로로 구성되어 있다.너의 임무는 가장 남쪽 길에서 가장 북쪽 길로 가서 지나가는 길의 기쁨치와 최대치를 가져오는 것이다. (기쁨치가 마이너스일 수도 있다.)같은 길은 두 번 지나갈 수 없고 북쪽에서 남쪽으로 갈 수 없다.또한 모든 횡단보도에서 소비하는 시간은 k를 초과해서는 안 된다.
문제풀이 방향: dp[i][j][0]는 (i, j)이라는 위치로 가는 최대 기쁨치를 나타내고, dp[i][j][1]는 왼쪽에서 (i, j)로 이동하는 최우수치를 나타내며, dp[i][j][2]는 오른쪽에서 (i, j)로 이동하는 최우수치를 나타낸다.
dp[i][j][1] = min { dp[i-1][k][0] + gay[i][j][1] - gay[i][k][1] | dis[i][j][1] - dis[i][k][1] <= k }
dp[i][j][1] = min { dp[i-1][k][0] + gay[i][j][2] - gay[i][k][2] | dis[i][j][2] - dis[i][k][2] <= k }
그러나 j마다 모든 k를 직접 고려한다면 복잡도는 o(n*m^2)이기 때문에 단조로운 대기열 최적화를 추가해야 한다.
dp[i-1][k][0] + gay[i][j][s] - gay[i][k][s] = gay[i][j][s] - (gay[i][k][s] - dp[i-1][k][0]);
func(i,k,s)=gay[i][k][s]-dp[i-1][k][0];그럼 func의 단조로움을 보호하기 위해서만 하면 됩니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 105;
const int M = 1e4+10;
const int INF = 0x3f3f3f3f;

int n, m, k, h[M], d[M];
int gay[N][M][3], dis[N][M][3], dp[N][M][3];

void init () {
	n++;
	memset(gay, 0, sizeof(gay));
	memset(dis, 0, sizeof(dis));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &h[j]);
			gay[i][j][1] = gay[i][j-1][1] + h[j];
		}
		for (int j = m-1; j >= 0; j--)
			gay[i][j][2] = gay[i][j+1][2] + h[j+1];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &d[j]);
			dis[i][j][1] = dis[i][j-1][1] + d[j];
		}
		for (int j = m-1; j >= 0; j--)
			dis[i][j][2] = dis[i][j+1][2] + d[j+1];
	}
}

int func(int i, int j, int o) {
	return gay[i][j][o] - dp[i-1][j][0];
}

int solve () {
	int ans = -INF;
	deque<int> que;

	for (int i = 1; i <= n; i++) {
		que.clear();
		for (int j = 0; j <= m; j++) {
			while (!que.empty() && dis[i][j][1] - dis[i][que.front()][1] > k) que.pop_front();
			while (!que.empty() && func(i, que.back(), 1) >= func(i, j, 1)) que.pop_back();
			que.push_back(j);
			dp[i][j][1] = gay[i][j][1] - func(i, que.front(), 1);
		}

		que.clear();
		for (int j = m; j >= 0; j--) {
			while (!que.empty() && dis[i][j][2] - dis[i][que.front()][2] > k) que.pop_front();
			while (!que.empty() && func(i, que.back(), 2) >= func(i, j, 2)) que.pop_back();
			que.push_back(j);
			dp[i][j][2] = gay[i][j][2] - func(i, que.front(), 2);
		}

		for (int j = 0; j <= m; j++)
			dp[i][j][0] = max(dp[i][j][1], dp[i][j][2]);
	}

	for (int i = 0; i <= m; i++)
		ans = max(ans, dp[n][i][0]);
	return ans;
}

int main () {
	while (scanf("%d%d%d", &n, &m, &k) == 3 && n + m + k) {
		init();
		printf("%d
", solve());
	}
	return 0;
}