Description：

有一个 $2\times n$ 的网格图，每个点上有一个数字 $a$ ，在相邻的格子之间连边，求出一个生成树最小化： $$ \sum_{i=1}^{2n}\sum_{j=i+1}^{2n}a_ia_jdis(i,j) $$ $1\leqslant t\leqslant 80,1\leqslant n\leqslant 50$

Solution：

考虑每一条边的贡献，会发现是两侧 $a_i$ 之和的乘积，考虑列之间的连边情况，可能会有一些列上下两行都连起来了，我们把相邻的上下都被连起来的列连起来，这样会连成一些连通块，每一个这样的连通块中间一定只有一个列上下之间连了起来，那么我们就可以考虑按这样的列的连通块转移，设 $f[i][0/1]$ 表示到了 $i$ ，与外界的连边在上面 $/$ 下面，那么转移为： $$ f[n][i]=\min(f[m-1][j]+\text{cost}(m,n,i,j)) $$ 这个 $\text{cost}$ 可以用 $O(n)$ 求，具体来说就是计算每条边的贡献。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 60

typedef long long ll;

ll suma = 0;

ll a[2][MAXN],s[2][MAXN],ss[MAXN];

ll f[MAXN][2];

ll v[MAXN][2][2];

ll val[MAXN][2];

ll sum(int l,int r,int tp){return s[tp][r] - s[tp][l - 1];}

ll ssum(int l,int r){return ss[r] - ss[l - 1];}

ll calc(ll half){return half * (suma - half);}

ll cost(int l,int r,int tpl,int tpr)

{

	ll sum0 = 0,sum1 = 0;

	for(int i = l;i < r;++i)

	{

		v[i][0][0] = calc(tpr == 0 ? ssum(r + 1,n) + sum(i + 1,r,0) : sum(i + 1,r,0));

		v[i][1][0] = calc(tpr == 1 ? ssum(r + 1,n) + sum(i + 1,r,1) : sum(i + 1,r,1));

		v[i][0][1] = calc(tpl == 0 ? ssum(1,l - 1) + sum(l,i,0) : sum(l,i,0));

		v[i][1][1] = calc(tpl == 1 ? ssum(1,l - 1) + sum(l,i,1) : sum(l,i,1));

		val[i][0] = v[i][0][0] + v[i][1][0];

		val[i][1] = v[i][0][1] + v[i][1][1];

		sum0 += val[i][0];

	}

	ll res = 0x3f3f3f3f3f3f3f3f;

	ll topval = sum(l,r,0),botval = sum(l,r,1);

	if(tpl == 0)topval += ssum(1,l - 1);

	if(tpl == 1)botval += ssum(1,l - 1);

	if(tpr == 0)topval += ssum(r + 1,n);

	if(tpr == 1)botval += ssum(r + 1,n);

	ll midval = topval * botval;

	for(int i = l;i <= r;++i)

	{

		res = min(res,sum0 + sum1);

		sum0 -= val[i][0];

		sum1 += val[i][1];

	}

	ll ans = res + midval + calc(ssum(1,l - 1));

	return ans;

}

void work()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[0][i]);

	for(int i = 1;i <= n;++i)scanf("%d",&a[1][i]);

	for(int i = 1;i <= n;++i)s[0][i] = s[0][i - 1] + a[0][i];

	for(int i = 1;i <= n;++i)s[1][i] = s[1][i - 1] + a[1][i];

	for(int i = 1;i <= n;++i)ss[i] = s[0][i] + s[1][i];

	suma = ss[n];

	memset(f,0x3f,sizeof(f));

	f[0][0] = f[0][1] = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= i;++j)

		{

			f[i][0] = min(f[i][0],min(f[j - 1][0] + cost(j,i,0,0),f[j - 1][1] + cost(j,i,1,0)));

			f[i][1] = min(f[i][1],min(f[j - 1][0] + cost(j,i,0,1),f[j - 1][1] + cost(j,i,1,1)));

		}

	}

	cout << min(f[n][0],f[n][1]) << endl;

	return;

}

int main()

{

	freopen("sum.in","r",stdin);

	freopen("sum.out","w",stdout);

	int testcases = rd();

	while(testcases--)work();

	fclose(stdin);

	fclose(stdout);

	return 0;

}