Yet Another Minimization Problem（CF1637D）-526互联

$\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';
}