继续作死就是不想写C#大作业 嘤嘤嘤 继虚拟机安不上、数据库连不上、网不好使之后，居然codeblocks都罢工==

这是一个长得像博弈的记忆化搜索（当然有人说是用博弈写的，代码居然还是这；还有人用区间dp写的 ，等学到那里再说）开始我就各种纠结怎么表示、怎么递归状态啊 。二呵呵的写了两个函数分别调用表示两个人依次取数的过程，仨人还得写仨函数呗→_→既然每个人都默认是聪明的，那么他俩每步取得过程都是按当前最优！几个人都是一样的！

Dp值表示剩下这些数里能取的最大值，继续的讲解我再想……估计今天又不想写大作业了


/******
hdu4597
2015.12.20-12.21
93MS 4892K 1240 B C++
*****/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int sum,t,n,num1[30],num2[30],dp[30][30][30][30];
int dfs(int la,int ra,int lb,int rb,int sum)
{
    if(dp[la][ra][lb][rb]) return dp[la][ra][lb][rb];
    if(la>ra&&lb>rb) return 0;
    int maxn=0;
    if(la<=ra)
    {
        maxn=max(maxn,sum-dfs(la+1,ra,lb,rb,sum-num1[la]));
        maxn=max(maxn,sum-dfs(la,ra-1,lb,rb,sum-num1[ra]));
    }
    if(lb<=rb)
    {
        maxn=max(maxn,sum-dfs(la,ra,lb+1,rb,sum-num2[lb]));
        maxn=max(maxn,sum-dfs(la,ra,lb,rb-1,sum-num2[rb]));
    }
    dp[la][ra][lb][rb]=maxn;
    return maxn;
}
int main()
{
   // freopen("cin.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num1[i]);
            sum+=num1[i];
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num2[i]);
            sum+=num2[i];
        }
        memset(dp,0,sizeof(dp));
        dfs(1,n,1,n,sum);
        printf("%d\n",dp[1][n][1][n]);
    }
    return 0;
}