\(\text{Des}\)
You are given two arrays $ a $ and $ b $ , both of length $ n $ .
You can perform the following operation any number of times (possibly zero): select an index $ i $ ( $ 1 \leq i \leq n $ ) and swap $ a_i $ and $ b_i $ .
Let's define the cost of the array $ a $ as $ \sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2 $ . Similarly, the cost of the array $ b $ is $ \sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2 $ .
Your task is to minimize the total cost of two arrays.
\(\text{Sol}\)
由题意可知，要求的值是在将任意的 \(a_i\) 与 \(b_i\) 交换的前提下，最小的
\[\sum_{i=1}^{n}\sum_{j=i+1}^{n}(a_i+a_j)^2+\sum_{i=1}^{n}\sum_{j=i+1}^{n}(b_i+b_j)^2 \]那么，由该式可以推出
\[\begin{aligned} &=\sum_{i=1}^{n}\sum_{j=i+1}^na_i^2+\sum_{i=1}^{n}\sum_{j=i+1}^na_j^2+\sum_{i=1}^{n}\sum_{j=i+1}^n2a_ia_j+\sum_{i=1}^{n}\sum_{j=i+1}^{n}b_i^2+\sum_{i=1}^{n}\sum_{j=i+1}^{n}b_j^2+\sum_{i=1}^{n}\sum_{j=i+1}^{n}2b_ib_j\\ &=(n-1)\left(\sum_{i=1}^{n}a_i+\sum_{i=1}^{n}b_i\right)+\sum_{i=1}^{n}\sum_{j=i+1}^{n}2a_ia_j+\sum_{i=1}^{n}\sum_{j=i+1}^{n}2b_ib_j\\ &=\left[(n-1)\left(\sum_{i=1}^{n}a_i+\sum_{i=1}^{n}b_i\right)\right]+2\left[\sum_{i=1}^{n}a_i\left(\sum_{j=i+1}^{n}a_j\right)+\sum_{i=1}^{n}b_i\left(\sum_{j=i+1}^{n}b_j\right)\right]\\ &=\left[(n-1)\left(\sum_{i=1}^{n}a_i+\sum_{i=1}^{n}b_i\right)\right]+2\left[\sum_{i=1}^{n}a_i\left(\sum_{j=1}^{i-1}a_j\right)+\sum_{i=1}^{n}b_i\left(\sum_{j=1}^{i-1}b_j\right)\right]\\ \end{aligned} \]可以发现其中的 \((n-1)\left(\sum_{i=1}^{n}a_i+\sum_{i=1}^{n}b_i\right)\) 是作为一个定值出现的，所以我们只需要将 \(\left[\sum_{i=1}^{n}a_i\left(\sum_{j=1}^{i-1}a_j\right)+\sum_{i=1}^{n}b_i\left(\sum_{j=1}^{i-1}b_j\right)\right]\) 最小化即可。
这一点，利用动规解决。
在由第 \(i-1\) 个状态向第 \(i\) 个状态转移的时候，我们无法确定的是 \(\sum_{j=i+1}^na_i\) 和 \(\sum_{j=i+1}^nb_i\) 的值（因为其中可能存在交换）。
那么因为考虑到 \(\sum_{i=1}^na_i\) 的值并不大，所以可以将 \(\sum_{i=1}^{n}a_i\) 加入状态。
又因为交换的为 \(a_i\) 与 \(b_i\)，可以发现在相同范围内的区间和的和（即 \(\sum_{i=l}^{r}a_i+b_i\)）也是一个定值，那么就可以求出对应的 \(b\) 的区间的和。
此时，我们设计状态为 \(f(i,j)\) 表示为考虑前 \(i\) 位，\(\sum_{k=1}^{i}a_k=j\) 时的最小值，那么有
\[{f(i,j)=\min\begin{cases} f(i-1,j-b_i)+b_i\times(j-b_i)+a_i\times\left[\sum_{k=1}^{i-1}\left(a_k+b_k\right)-\left(j-b_i\right)\right],&\text{if swap(a,b)}\\ f(i-1,j-a_i)+a_i\times(j-a_i)+b_i\times\left[\sum_{k=1}^{i-1}\left(a_k+b_k\right)-\left(j-a_i\right)\right],&\text{elsewise} \end{cases}} \]\(\text{CODE}\)
void solve() {
ans=minn=0;
memset(f,0x7f7f7f,sizeof(f));
f[0][0]=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) {
cin>>b[i];
k[i]=k[i-1]+max(a[i],b[i]);
sum[i]=sum[i-1]+a[i]+b[i];
ans+=a[i]*a[i]+b[i]*b[i];
}
ans*=(n-1);
for(int i=1;i<=n;i++) {
for(int j=1;j<=k[i];j++) {
if (j-a[i]>=0 && sum[i-1]-j+a[i]>=0) {
f[i][j]=min(f[i][j],f[i-1][j-a[i]]+a[i]*(j-a[i])+b[i]*(sum[i-1]-j+a[i]));
}
if (j-b[i]>=0 && sum[i-1]-j+b[i]>=0){
f[i][j]=min(f[i][j],f[i-1][j-b[i]]+b[i]*(j-b[i])+a[i]*(sum[i-1]-j+b[i]));
}
}
}
minn=1e9+7;
for(int j=1;j<=k[n];j++){
minn=min(minn,f[n][j]);
}
cout<<ans+2*minn<<'\n';
}