本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-11 17:37:06

题意：

有 $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)$

$S_{(a_1,a_2,a_3)}$ $\Longrightarrow$ $S_{(a_1,a_2,a_3,a_4)}$ 他们有什么不同的地方呢？

其实他就是加上了 $a_4 (a_1 + a_2 + a_3)$

所以，我们就可以进行 DP 了。

因为我们只需要存 $a_1 + a_2 + a_3 ... + a_n$ 的 $sum$。

$dp_{sumA,sumB,i}$ 表示分配了 $a_1 ... a_i$，$b_1 ... b_i$ 为 $S_{(a_1 ... a_i)} + S_{(b_1 ... b_i)}$（$S$ 之前定义过了）。

就是当 $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;
}