글 읽기 - 왜 틀렸는지 모르겠습니다

hwa3060 3년 전 0

누적합 전처리로 구해놓고 오른쪽 왼쪽 아래 중에 최대값 구하는 것을 재귀로 풀었는데 틀렸습니다가 나옵니다.

혹시 틀린부분이나 반례를 알수있을까요?

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int R, C;

int a[1501][1501];
int b[1501][1501];
int cache[1501][1501];

int DP(int x, int y)
{
	int& ret = cache[x][y];
	if (ret != -1)
	{
		return ret;
	}


	if (x == R - 1 && y == C - 1)
	{
		return ret = b[x-1][y];
	}
	else if (x == R - 1)
	{
		return ret = DP(x, y + 1) + a[R-1][y] - a[x][y] + b[x-1][y];
	}
	else if (y == C - 1)
	{
		return ret = DP(x + 1, y) - (b[x][y] - b[x-1][y]);
	}

	return ret = max(DP(x + 1, y) -  (b[x][y] - b[x-1][y]), max(DP(x, y + 1) +  a[R-1][y] - a[x][y] + b[x-1][y], DP(x + 1, y + 1) +  a[R-1][y] - a[x][y] + b[x-1][y]));
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> R >> C;


	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			char c;
			int n;

			cin >> c >> n;

			if (c == 'A') {
				a[i][j] = n;
			}
			else if (c == 'B') {
				b[i][j] = n;
			}
		}
	}

	for (int i = 1; i < R; i++) {
		for (int j = 0; j < C; j++) {
			a[i][j] += a[i - 1][j]; 
			b[i][j] += b[i - 1][j]; 
		}
	}


	memset(cache, -1, sizeof(cache));

	DP(0, 0);

	cout << cache[0][0] << endl;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다

hwa3060 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말