题目翻译

Alice 和 Bob 在玩游戏。

有两堆卡片。每一堆有 $n$ 张牌，每一张牌都有一个分数。

他们轮流从任何一堆中拿起最上面或最下面的一张牌，这张牌的分数将加到他的总分中。

Alice 和 Bob都够聪明，他们都会以最优方式拿起卡片从而尽可能多地得分。

请你求出来如果 Alice 先手能得多少分。

分析

题目中告诉我们取牌必须从序列的两段取出，故我们保留的牌堆一定是一段连续的区间

设 $f[i][j][l][r]$ 表示对于第一堆牌保留的区间为 $i$ 到 $j$ ，第二堆保留的为 $l$ 到 $r$ 时 Alice 的最大得分。

递推的话需要考虑的情况较多，故我们采用记忆化搜索实现代码。

但在搜索时有一个细节：每一次拓展时取牌的人会更换，故拓展时拓展出的是 Bob 所能获得的最大得分。而最后 Alice 的得分是总分数减去 Bob 的分数。故最后的答案是：

$ans = max \lbrack sum - dfs(sum - tot) \rbrack$

其中 $tot$ 为被取走的牌，需要分四种情况进行讨论。

剩下的细节详见代码。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

int n , a[M] , b[M] , f[30][30][30][30];

//f[i][j][l][r] 对于第一堆牌保留的区间为 $i$ 到 $j$ ，第二堆保留的为 $l$ 到 $r$ 时先手的最大得分

int dfs(int al , int ar , int bl , int br , int sm){    
	if(f[al][ar][bl][br]) return f[al][ar][bl][br];    //如果已经搜到过，则直接返回结果
	if(al > ar && bl > br) return 0;    //若无牌可取，则返回0
	int ans = 0;
	if(al <= ar){    
		ans = max(ans , sm - dfs(al + 1 , ar , bl , br , sm - a[al])); 
		//注意：此时拓展的为 Bob 的最大得分，而 Alice 的最大得分为 sm - Bob的最大得分，
		ans = max(ans , sm - dfs(al , ar - 1 , bl , br , sm - a[ar]));
	}
	if(bl <= br){
		ans = max(ans , sm - dfs(al , ar , bl + 1 , br , sm - b[bl]));
		ans = max(ans , sm - dfs(al , ar , bl , br - 1 , sm - b[br]));
	}
	f[al][ar][bl][br] = ans;
	return ans;
}

void solve(){
	read(n);
	ll sm = 0;
	rep(i , 1 , n) read(a[i]) , sm += a[i];
	rep(i , 1 , n) read(b[i]) , sm += b[i];
	
	clean(f , 0);
	ll res = dfs(1 , n , 1 , n , sm);
	printf("%d\n" , res);
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
	int t; read(t);
	while(t --) solve();

    return 0;
}