当前位置：首页 > news >正文

Codeforces Global Round 19 D题 Yet Another Minimization Problem（推式子，01背包变形）

news 2024/11/15 14:50:15

题目链接

https://codeforces.com/problemset/problem/1637/D

思路

对于原式子进行推导

$\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}$

$=$ $\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}))$

可以发现， $\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}))$ 的最小值即可。

我们定义 $\sum_{j=1}^{i} a_{j} + \sum_{j=1}^{i} b_{j}$

考虑使用 $d p$ 。我们定义 $d p [i] [j]$ 表示只考虑前 $i$ 位时， $a$ 数组的背包容量为 $j$ 时的最小值。（先不考虑系数 $2$ ，因此最后的结果为答案的一半）。

若不交换 $a_{i}$ 和 $b_{i}$ ，则状态转移方程为：

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

若交换 $a_{i}$ 和 $b_{i}$ ，则状态转移方程为：

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

最终的答案即为： $\sum_{i=1}^{n} \sum_{j=i+1}^{n}(a_{i}^{2}+ a_{j}^{2}+b_{i}^{2}+b_{j}^{2})$ $+$ $min_{i=1}^{max}dp_{n,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;
}