DP ACdream 야옹야옹 마을의 도발

가슴이 답답하다 기억화 수색 가르치다 처음 보다
아침 내내 dp를 썼는데도 전이 방정식을 제대로 쓰지 못했다

/********************************************
Author         :Crystal
Created Time   :
File Name      :
********************************************/
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
int a[30];
int sa[30];
int sb[30];
int b[30];
int dp[30][30][30][30];
int nmin = 0;
int dfs(int x,int y,int u,int v){
	//     
	if(dp[x][y][u][v]>=0)return dp[x][y][u][v];
	int sum = 0;
	int ret = 0;
	if(x <= y)sum += sa[y]-sa[x-1];
	if(u <= v)sum += sb[v]-sb[u-1];
	if(x<=y)ret = max(ret,sum - min(dfs(x+1,y,u,v),dfs(x,y-1,u,v)));
	if(u<=v)ret = max(ret,sum - min(dfs(x,y,u+1,v),dfs(x,y,u,v-1)));
	return dp[x][y][u][v] = ret;//      
}
int main()
{
	int n;
	while(scanf("%d",&n) != EOF){
		memset(dp,-1,sizeof dp);
		for(int i=1;i<=n;i++)cin >> a[i];
		for(int i=1;i<=n;i++)cin >> b[i];
		for(int i=1;i<=n;i++){
			sa[i]=sa[i-1]+a[i];
			sb[i]=sb[i-1]+b[i];
		}
		nmin = dfs(1,n,1,n);
		cout << nmin << endl;
	}
	return 0;
}