解析:
两人都绝对聪明,Alice先走,尽量让Bob所能拿的分数最少,Alice有一次往下走的机会,剩余没走过的点正好分为两断断开的区域,所以Bob的最大分数要么在第一格向下或者在最后一列向下。
遍历区间,枚举Alice向下的格子,统计Bob的最小分数即为答案。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int t,n,a[N],b[N],suma[N],sumb[N];
signed main(){scanf("%lld",&t);while(t--){scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);suma[i]=suma[i-1]+a[i];}for(int i=1;i<=n;i++){scanf("%lld",&b[i]);sumb[i]=sumb[i-1]+b[i];}int res=0x3f3f3f3f;for(int i=1;i<=n;i++){int s1=suma[n]-suma[i];int s2=sumb[i-1];res=min(res,max(s1,s2));}printf("%lld\n",res);}return 0;
}