Codeforces Round #131 (Div. 2) E. Relay Race

제목의 뜻
n*n(1<=n<=300)의 정사각형 행렬을 드리겠습니다. 이제 (1,1)에서 (n,n)까지, 그리고 (n,n)에서 (1,1)까지 경로에 있는 모든 값과 최대가 얼마입니까?행렬에서 요소당 최대 1회
주법 제한:
1. (1,1)에서 (n,n): 아래로 또는 오른쪽으로만 갈 수 있다.
2, (n, n)에서 (1, 1): 위로 또는 왼쪽으로만 갈 수 있다
방법 분석
고전적 동태 기획의 변형은 사실 간단하게 변했다...남들은 원래 두 가지 경로가 겹치지 못하도록 요구했는데, 지금은 겹칠 수 있는 것으로 바뀌었다. 물론 고려할 것이 비교적 적을 뿐이다
먼저 하나의 예시를 보겠습니다. n=5:
        
우리는 문제를 두 사람이 동시에 (1,1), (n,n)을 향해 걸어간다. 걸어가는 과정에서 같은 곳에 가면 그곳의 값을 한 번만 얻는다. 그러면 우리는 위의 그림을 얻기 어렵지 않다. 한 걸음 한 걸음 걸어온 위치가 몇 개이고 단계의 구분은 바로 지금 몇 단계까지 갔는지 알 수 있다. 상태는 다음과 같다. f[i][a]: i단계에 이르렀다.첫 번째 사람의 위치는 a이고 두 번째 사람의 위치는 b이다. 그 중에서 a, b는 위의 첫 번째 그림에서 화살표의 방향에 따라 번호를 매긴다. 즉, 두 번째 그림에서 보여준 것처럼 a, b는 1, 2, 3, 4...
위의 그림과 비교하면 상태 사이의 전이 방정식은 쓰기 어렵지 않다.
1. 현재 걸음수가 n보다 작을 때: 각 a는 이전 걸음의 a 또는 a-1에서 얻는다.
매 b는 이전 b나 b-1에서 얻는다
물론 이전 단계에서 a와 a-1, b와 b-1이 합법적인지 판단해야 한다(매트릭스 범위 초과)
조합하면 네 가지 상태.
2. 현재 스텝 수가 n보다 클 때:
매 a는 이전 a나 a+1에서 얻을 수 있다
각 b는 이전 단계의 b 또는 b+1에서 얻을 수 있다
조합하면 네 가지 상태.
각각 해답을 구하면 된다. 걸음수는 2*n-1걸음이기 때문에 걸음마다 최대 n개가 있고 n의 최대치는 300이다. 그래서 600*300*300*4의 메모리 공간이 필요하다. 분명히 부족하다. 그래서 스크롤 수조로 메모리를 300*300*4로 바꾸었다.
AC 채널
Codeforces Round #131 (Div. 2) E. Relay Race
참조 코드

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N=305;
const int INT_INF=0x3fffffff;

int val[N][N], n, f[2][2*N][2*N];

int Max(int i)
{
	if(i<=n) return i;
	else return 2*n-i;
}

int get_val(int i, int a)
{
	if(i<=n) return val[i-a+1][a];
	else return val[n-a+1][i-n+a];
}

int main()
{
	while(~scanf("%d", &n))
	{
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				scanf("%d", &val[i][j]);
		memset(f, 0, sizeof(f));
		f[1][1][1]=val[1][1];
		for(int i=2; i<=n; i++)
		{
			int len=Max(i);
			for(int a=1; a<=len; a++)
				for(int b=1; b<=len; b++)
				{
					int cnt=-INT_INF;
					if(a!=1 && b!=1) cnt=max(cnt, f[(i+1)%2][a-1][b-1]);
					if(a!=1 && b!=len) cnt=max(cnt, f[(i+1)%2][a-1][b]);
					if(a!=len && b!=1) cnt=max(cnt, f[(i+1)%2][a][b-1]);
					if(a!=len && b!=len) cnt=max(cnt, f[(i+1)%2][a][b]);
					if(a!=b) f[i%2][a][b]=cnt+get_val(i, a)+get_val(i, b);
					else f[i%2][a][b]=cnt+get_val(i, a);
				}
		}
		for(int i=n+1; i<=2*n-1; i++)
		{
			int len=Max(i);
			for(int a=1; a<=len; a++)
				for(int b=1; b<=len; b++)
				{
					int cnt=-INT_INF;
					cnt=max(cnt, f[(i+1)%2][a+1][b]);
					cnt=max(cnt, f[(i+1)%2][a+1][b+1]);
					cnt=max(cnt, f[(i+1)%2][a][b]);
					cnt=max(cnt, f[(i+1)%2][a][b+1]);
					if(a!=b) f[i%2][a][b]=cnt+get_val(i, a)+get_val(i, b);
					else f[i%2][a][b]=cnt+get_val(i, a);
				}
		}
		printf("%d
", f[1][1][1]);
	}
	return 0;
}