题目链接
https://codeforces.com/problemset/problem/1637/D
思路
对于原式子进行推导
∑ i = 1 n ∑ j = i + 1 n ( a i + a j ) 2 + ∑ i = 1 n ∑ j = i + 1 n ( b i + b j ) 2 \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} ∑i=1n∑j=i+1n(ai+aj)2+∑i=1n∑j=i+1n(bi+bj)2
= = = ∑ i = 1 n ∑ j = i + 1 n ( a i 2 + a j 2 + b i 2 + b j 2 ) + ∑ i = 1 n ∑ j = i + 1 n ( 2 × ( a i a j + b i b j ) ) \sum_{i=1}^{n} \sum_{j=i+1}^{n}(a_{i}^{2}+ a_{j}^{2}+b_{i}^{2}+b_{j}^{2}) + \sum_{i=1}^{n} \sum_{j=i+1}^{n}(2 \times (a_{i}a_{j}+b_{i}b_{j})) ∑i=1n∑j=i+1n(ai2+aj2+bi2+bj2)+∑i=1n∑j=i+1n(2×(aiaj+bibj))
可以发现， ∑ i = 1 n ∑ j = i + 1 n ( a i 2 + a j 2 + b i 2 + b j 2 ) \sum_{i=1}^{n} \sum_{j=i+1}^{n}(a_{i}^{2}+ a_{j}^{2}+b_{i}^{2}+b_{j}^{2}) ∑i=1n∑j=i+1n(ai2+aj2+bi2+bj2)是一个定值，我们只需要计算 ∑ i = 1 n ∑ j = i + 1 n ( 2 × ( a i a j + b i b j ) ) \sum_{i=1}^{n} \sum_{j=i+1}^{n}(2 \times (a_{i}a_{j}+b_{i}b_{j})) ∑i=1n∑j=i+1n(2×(aiaj+bibj))的最小值即可。
我们定义 s u m [ i ] = ∑ j = 1 i a j + ∑ j = 1 i b j sum[i] = \sum_{j=1}^{i} a_{j} + \sum_{j=1}^{i} b_{j} sum[i]=∑j=1iaj+∑j=1ibj
考虑使用 d p dp dp。我们定义 d p [ i ] [ j ] dp[i][j] dp[i][j]表示只考虑前 i i i位时， a a a数组的背包容量为 j j j时的最小值。（先不考虑系数 2 2 2，因此最后的结果为答案的一半）。
若不交换 a i a_{i} ai和 b i b_{i} bi，则状态转移方程为：
d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i − 1 ] [ j − a [ i ] ] + a [ i ] ∗ ( j − a [ i ] ) + b [ i ] ∗ ( s u m [ i − 1 ] − j + a [ i ] ) ) dp[i][j] = min(dp[i][j], dp[i - 1][j - a[i]] + a[i] * (j - a[i]) + b[i] * (sum[i - 1] - j + a[i])) dp[i][j]=min(dp[i][j],dp[i−1][j−a[i]]+a[i]∗(j−a[i])+b[i]∗(sum[i−1]−j+a[i]))
若交换 a i a_{i} ai和 b i b_{i} bi，则状态转移方程为：
d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i − 1 ] [ j − b [ i ] ] + b [ i ] ∗ ( j − b [ i ] ) + a [ i ] ∗ ( s u m [ i − 1 ] − j + b [ i ] ) ) dp[i][j] = min(dp[i][j], dp[i - 1][j - b[i]] + b[i] * (j - b[i]) + a[i] * (sum[i - 1] - j + b[i])) dp[i][j]=min(dp[i][j],dp[i−1][j−b[i]]+b[i]∗(j−b[i])+a[i]∗(sum[i−1]−j+b[i]))
最终的答案即为： ∑ i = 1 n ∑ j = i + 1 n ( a i 2 + a j 2 + b i 2 + b j 2 ) \sum_{i=1}^{n} \sum_{j=i+1}^{n}(a_{i}^{2}+ a_{j}^{2}+b_{i}^{2}+b_{j}^{2}) ∑i=1n∑j=i+1n(ai2+aj2+bi2+bj2) + + + m i n i = 1 m a x d p n , i min_{i=1}^{max}dp_{n,i} mini=1maxdpn,i
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 5, M = 1e4 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[N], b[N], sum[N], dp[N][M];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}int ans = 0;for (int i = 1; i < n; i++){for (int j = i + 1; j <= n; j++){ans += (pow(a[i], 2) + pow(a[j], 2));ans += (pow(b[i], 2) + pow(b[j], 2));}}for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] + a[i] + b[i];}for (int i = 1; i <= n; i++){for (int j = 0; j <= 1e4; j++){dp[i][j] = inf;}}dp[0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= 1e4; j++){if (j >= a[i] && (sum[i - 1] - j + a[i]) >= 0)dp[i][j] = min(dp[i][j], dp[i - 1][j - a[i]] + a[i] * (j - a[i]) + b[i] * (sum[i - 1] - j + a[i]));if (j >= b[i] && (sum[i - 1] - j + b[i]) >= 0)dp[i][j] = min(dp[i][j], dp[i - 1][j - b[i]] + b[i] * (j - b[i]) + a[i] * (sum[i - 1] - j + b[i]));}}int res = inf;for (int i = 1; i <= 1e4; i++)res = min(res, dp[n][i]);cout << ans + res * 2 << endl;}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}
