【Codeforces】1637D Yet Another Minimization Problem题解

题目大意

给定 $n$（$1 \le n \le 100$）对数 $a, b$（$1 \le a_i, b_i \le 100$），可以对每对 $(a_i, b_i)$ 进行交换。求：

$$\sum_{i=1}^n\sum_{j=i+1}^n\left[(a_i+a_j)^2+(b_i+b_j)^2\right]$$

的最小值。

题目地址

思路

直接计算很耗费时间且无法找到合适的求最小值方法，所以我们试试化简这个式子。

我们先看 $a$ 数组。定义 $sumA = \sum_{i=1}^n a_i$，则：

$$\sum_{i=1}^n\sum_{j=i+1}^n(a_i+a_j)^2 = (n-1)\sum_{i=1}^{n}a_i^2 + \sum_{i=1}^n(a_i \cdot (sumA - a_i))$$ $$= (n-1)\sum_{i=1}^{n}a_i^2 + \sum_{i=1}^n(a_i \cdot sumA - a_i^2)$$ $$= (n-2)\sum_{i=1}^{n}a_i^2 + sumA^2$$

所以问题就变成了求：

$$(n-2)\sum_{i=1}^{n}(a_i^2 + b_i^2) + sumA^2 + sumB^2$$

的最小值，即求 $\min{sumA^2 + sumB^2}$。

由于 $(n-2)\sum(a_i^2 + b_i^2)$ 交换后不变，所以我们只需要枚举所有 $sumA, sumB$ 的可能值。

令 $a_i \le b_i$（对 $\min(a_i, b_i)$ 计入 $sumA$，$\max(a_i, b_i)$ 计入 $sumB$），令 $c_i = b_i - a_i$。那么：

$$sumA' = sumA + \sum_{i \in S} c_i,\quad sumB' = sumB - \sum_{i \in S} c_i$$

我们可以用背包 DP 的方式去枚举 $\sum c_{i,j,k,\ldots}$ 的所有可能值。由于 $c_i$ 的值域较小，可以直接用 bitset 来简化操作。

时间复杂度 $O(n^2 \cdot \max{a_i})$。

代码

#include <cstdio>
#include <iostream>
#include <bitset>
using namespace std;

int T, n, a[105], b[105];

int main()
{
    scanf("%d", &T);
    while(T--) {
        int minSum = 0, maxSum = 0, rSum = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &b[i]);
        for(int i = 1; i <= n; ++i) {
            if(a[i] > b[i])
                swap(a[i], b[i]);
            minSum += a[i];
            maxSum += b[i];
            rSum += a[i] * a[i] + b[i] * b[i];
        }
        bitset<105 * 105> dp;
        dp[0] = 1;
        for(int i = 1; i <= n; ++i)
            dp |= dp << (b[i] - a[i]);
        int ans = maxSum * maxSum + minSum * minSum;
        for(int i = 0; i < maxSum - minSum; ++i)
            if(dp[i])
                ans = min(ans, (maxSum - i) * (maxSum - i) + (minSum + i) * (minSum + i));
        printf("%d\n", (n - 2) * rSum + ans);
    }
    return 0;
}