D. Yet Another Minimization Problem(dp,数学公式推导)

本文主要是介绍D. Yet Another Minimization Problem(dp,数学公式推导)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given two arrays aa and bb, both of length nn.

You can perform the following operation any number of times (possibly zero): select an index ii (1≤i≤n1≤i≤n) and swap aiai and bibi.

Let's define the cost of the array aa as ∑ni=1∑nj=i+1(ai+aj)2∑i=1n∑j=i+1n(ai+aj)2. Similarly, the cost of the array bb is ∑ni=1∑nj=i+1(bi+bj)2∑i=1n∑j=i+1n(bi+bj)2.

Your task is to minimize the total cost of two arrays.

Input

Each test case consists of several test cases. The first line contains a single integer tt (1≤t≤401≤t≤40) — the number of test cases. The following is a description of the input data sets.

The first line of each test case contains an integer nn (1≤n≤1001≤n≤100) — the length of both arrays.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100) — elements of the first array.

The third line of each test case contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1001≤bi≤100) — elements of the second array.

It is guaranteed that the sum of nn over all test cases does not exceed 100100.

Output

For each test case, print the minimum possible total cost.

Example

input

Copy

3
1
3
6
4
3 6 6 6
2 7 4 1
4
6 7 2 4
2 5 3 5

output

Copy

0
987
914

Note

In the second test case, in one of the optimal answers after all operations a=[2,6,4,6]a=[2,6,4,6], b=[3,7,6,1]b=[3,7,6,1].

The cost of the array aa equals to (2+6)2+(2+4)2+(2+6)2+(6+4)2+(6+6)2+(4+6)2=508(2+6)2+(2+4)2+(2+6)2+(6+4)2+(6+6)2+(4+6)2=508.

The cost of the array bb equals to (3+7)2+(3+6)2+(3+1)2+(7+6)2+(7+1)2+(6+1)2=479(3+7)2+(3+6)2+(3+1)2+(7+6)2+(7+1)2+(6+1)2=479.

The total cost of two arrays equals to 508+479=987508+479=987.

思路:

参考:

代码:

int a[maxj],b[maxj];
void solve() {int n;int dp[maxj];//一维滚动数组提高效率cin>>n;int all=0,resa=0,sum=0,ans=0;rep(i,1,n){cin>>a[i];all+=a[i];}rep(i,1,n){cin>>b[i];all+=b[i];if(a[i]>b[i])swap(a[i],b[i]);resa+=a[i];ans+=a[i]*a[i];ans+=b[i]*b[i];b[i]-=a[i];sum+=b[i];}int m=sum/2;memset(dp,0,sizeof(dp));rep(i,1,n) {atp(j,m,b[i]) {dp[j]=max(dp[j],dp[j-b[i]]+b[i]);}}int suma=resa+dp[m],sumb=all-suma;ans=ans*(n-2)+suma*suma+sumb*sumb;cout<<ans<<'\n';
}

这篇关于D. Yet Another Minimization Problem(dp,数学公式推导)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---