CF1637D题解
FiraCode
·
·
题解
题意：
有 A,B 两个序列，长度为 n。
定义一个序列 a_1 , a_2 ... a_n。
他的价值： 为 \sum^{n}_{i=1} \sum^{n}_{j=i+1} (a_i + a_j) ^ 2
我们可以交换 a_i,b_i 的位置。
最后求 A 的价值 + B 的价值最小。
题解思路：
先把计算价值的式子拆一下变成：
k_1 (\sum^{n}_{i=1}a_i ^ 2) + k_2 (\sum^{n}_{i=1} \sum^{n}_{j=i+1}a_i \times a_j)
已知 k_1 = n - 1 , k_2 = 2\
=(n-1)(\sum^{n}_{i=1}a_i ^ 2) + 2(\sum^{n}_{i=1} \sum^{n}_{j=i+1}a_i \times a_j)
我们可以发现，不论我们怎么改，a_i 乘方的次数是不变的。
但我们能改变 a_i \times a_j 的次数
我们定义 S_a 为他们两两想乘的结果
设一个序列为：(a_i , a_2 , a_3)
其实他就是加上了 $a_4 (a_1 + a_2 + a_3)
所以，我们就可以进行 DP 了。
因为我们只需要存 a_1 + a_2 + a_3 ... + a_n 的 sum。
就是当 $a_1 + a_2 + ... + a_i = sumA$ 并且 $b_1 + b_2 + ... + b_i = sumB$ 并且分配了前 $i$ 情况下 $S$ 的最小值。
当我们给 $a$ 序列增加一个 $x$，给 $b$ 序列增加一个 $y$ 时，$dp_{sumA,sumB}$ 其实就是加上 $x \times sumA , y \times sumB$。
实际上 $sumB$ 这一维是不需要的，因为我们有了 $dp_i$ 了，那么我们就知道了 $sumA + sumB$，我们就可以直接算出 $sumB$ 的值了。
其实 $dp_{sumA,sumB,i}$ 有很多是无意义的。
就比如 $sumA + sumB \ne (a_1 + a_2 + ... + a_n + b_1 + b_2 + ... + b_n)$，那么 $dp_{sumA , sumB , i}$ 就是无意义的。
那我们就删掉一维，因为 $sumA$ 只有一个唯一对应的一个 $sumB$，我们就把 $sumB$ 这一维压掉。
$O(n ^ 3)$ 个状态，转移时间为 $O(1)$，所以总时间复杂度为 $O(n ^ 3)$。
[【AC 记录】]()
## AC Code:
```
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110 , M = 20010;
const long long INF = 1e15;
int n;
int a[N] , b[N];
long long dp[M] , tmpdp[M];
int main() {
int T;
cin >> T;
while (T --) {
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 = 0; i <= 100 * n; ++ i) dp[i] = tmpdp[i] = INF;
tmpdp[0] = 0;
int Sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 100 * n; j++) {
int tmp1 = j, tmp2 = Sum - j;//算出sumA,sumB
if (tmpdp[j] == INF) continue;
dp[j + a[i]] = min(dp[j + a[i]], tmpdp[j] + a[i] * tmp1 + b[i] * tmp2);//用了滚数组优化
dp[j + b[i]] = min(dp[j + b[i]], tmpdp[j] + a[i] * tmp2 + b[i] * tmp1);
}
Sum += a[i] + b[i];
for (int j = 0; j <= 100 * n; j++) {
tmpdp[j] = dp[j];
dp[j] = INF;
}
}
long long sum1 = INF, sum2 = 0;
for (int i = 0; i <= 100 * n; i++) sum1 = min(sum1, tmpdp[i]);//看DP[sumA]最小的是多少
for (int i = 0; i <= n; i++) sum2 += (a[i] * a[i] + b[i] * b[i]);//就是平方的那个
printf("%lld\n", sum2 * (n - 1) + sum1 * 2);//输出答案
}
return 0;
}
```