cf1637D

题目大意

给定长度均为\(n(1 \le n \le 100)\)的数组\(a,b(1 \le a_i, b_i \le 100)\),可以任意交换\(a_i,b_i(1 \le i \le n)\) 求\(\sum_{i=1}^n\sum_{j=i+1}^n[(a_i+a_j)^2+(b_i + b_j)^2]\)的最小值。 题目地址

思路

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

我们先看\(a\)数组。 定义:\(sum_A = \sum_{i=1}^na_ik\) 原式\(=(n-1)\sum_{i=1}^{n}a_i^2 + \sum_{i=1}^n(a_i*(sum_A - a_i))\) \(=(n-1)\sum_{i=1}^{n}a_i^2 + \sum_{i=1}^n(a_i*sum_A - a_i * a_i)\) \(=(n-2)\sum_{i=1}^{n}a_i^2 + sum_A^2\)

所以问题就变成了求\((n-2)\sum_{i=1}^{n}(a_i^2 + b_i^2) + sum_A^2 + sum_B^2\)的最小值

即求\(min\{sum_A^2 + sum_B^2\}\)

所以我们打算求出所有\(sum_A,sum_B\)的可能值，来计算最小值。

我们把所有\(min(a_i,b_i)\)移到\(sum_A\),\(max(a_,b_i)\)移到\(sum_B\)。 令\(c_i = b_i-a_i\)。 那么\(sum_A' = sum_A + c_{i,j,k...},sum_B'=sum_B - c_{i,j,k...}\) 而我们可以用背包\(dp\)的方式去求\(c_{i,j,k}\),由于\(c_i\)的值域较小，我们可以直接用\(bitset\)来简化操作。

时间复杂度\(O(n^2*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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/03/02/cf1637D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！