考虑观察答案形态。
当 \(n, m\) 均为偶数时,前一半位置有 \(\frac{n}{2}\) 个是狗,\(\frac{m}{2}\) 个是猫。并且前半段从前往后和后半段从后往前都是按权值从小到大放。调整法证明即可。
当 \(n\) 或 \(m\) 为奇数时,把 \(a_i\) 或 \(b_i\) 最大的放中间,一定不劣。证明就是考虑,中间那个位置的 \(|l_i - r_i|\) 为 \(0\),所以一定是放最大的。
当 \(n, m\) 均为奇数时,把 \(a_i\) 或 \(b_i\) 最大的放中间,也一定不劣。
据此可以设计一个三次方 dp:\(f_{i, j, k}\) 表示考虑到权值前 \(i\) 小的小动物,前缀放了 \(j\) 个狗,\(k\) 个猫。转移平凡,考虑权值第 \(i\) 小的小动物放在前缀还是后缀即可。已经可以通过。
还有更优的线性对数做法。
code
// Problem: Ex - Bow Meow Optimization
// Contest: AtCoder - Toyota Programming Contest 2023 Spring Qual B(AtCoder Beginner Contest 290)
// URL: https://atcoder.jp/contests/abc290/tasks/abc290_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 310;
ll n, m, a[maxn], b[maxn], f[maxn << 1][maxn >> 1][maxn >> 1];
pii c[maxn << 1];
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i]);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
ll ans = 0;
if (n & 1) {
if (m & 1) {
ans += a[n];
}
for (int i = 1; i <= m; ++i) {
ans += b[i];
}
--n;
}
if (m & 1) {
for (int i = 1; i <= n; ++i) {
ans += a[i];
}
--m;
}
for (int i = 1; i <= n; ++i) {
c[i] = make_pair(a[i], 1);
}
for (int i = 1; i <= m; ++i) {
c[n + i] = make_pair(b[i], 0);
}
sort(c + 1, c + n + m + 1);
mems(f, 0x3f);
f[0][0][0] = 0;
int dog = 0, cat = 0;
for (int i = 1; i <= n + m; ++i) {
if (c[i].scd) {
++dog;
} else {
++cat;
}
for (int j = 0; j <= n / 2; ++j) {
for (int k = 0; k <= m / 2; ++k) {
if (c[i].scd) {
if (j) {
f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + c[i].fst * abs(k - (m - k)));
}
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + c[i].fst * abs(cat - k - (m - (cat - k))));
} else {
if (k) {
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] + c[i].fst * abs(j - (n - j)));
}
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + c[i].fst * abs(dog - j - (n - (dog - j))));
}
}
}
}
ans += f[n + m][n / 2][m / 2];
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Optimization Beginner AtCoder Contest Meowoptimization beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310