[ABC400G] Patisserie ABC 3

发表于 分类于 ， 阅读次数：
简单题。

Statement

给定正整数 \(n,k\) 和 \(n\) 个三元组 \((x_i,y_i,z_i)\)。

现要选出 \(k\) 个二元组 \((a_i,b_i)\)，满足每个位置只能出现一次，并要求最大化：

\[\sum_{i=1}^k\max\{x_{a_i}+x_{b_i},y_{a_i}+y_{b_i},z_{a_i}+z_{b_i}\}\]

输出这个最大值。

Data range：\(T\) 组多测，\(\sum n\le 10^5\)，\(2k\le n\)，\(0\le x_i,y_i,z_i\le 10^9\)。

Solution

首先你考虑每个数对答案的贡献。你发现每种数（指 \(x,y,z\)）的贡献都是成对的，所以肯定要求数量都是偶数。

而你发现偶数是充要的（两两配对就行，如果实际上不是这种数产生贡献那也肯定不是最优解），那么问题转化成了：

对于每个 \(i\) 可以选 \(x_i\)、选 \(y_i\)、选 \(z_i\) 或什么都不选，要求一共选 \(2k\) 个，且每种数都要选偶数个，求最大和。

这里就有了一个 \(\mathcal O(nk)\) 的做法了，就是 dp 记一下前 \(i\) 个里选了 \(j\) 个，\(x,y,z\) 分别有奇数/偶数个的最大和。

当然这是过不了的，考虑优化。

你发现偶数这个限制很松，即使不符合稍微调一下也能符合。

那你考虑按 \(\max\{x_i,y_i,z_i\}\) 从大到小排序。

然后会有一个结论：最终方案中，前 \(2k\) 个里面最多有两个不选（被调整成后面的至多两个，注意前面的选了并不一定是最大的那个）。

证明：

假设前面的有三个没选，那么对应的后面会选了三个。

我们称一个前面的没选的 \(x_i\) 最大的位置为 \(\texttt X\) 类，\(\texttt Y,\texttt Z\) 类同理；后面的选了 \(x_i\) 的位置为 \(\texttt x\) 类，\(\texttt y,\texttt z\) 类同理。

那么：

  1. 显然不可能同时出现 \(\texttt X,\texttt x\) 类，因为可以直接替换掉，其他的同理。
  2. 也不可能同时出现两个 \(\texttt X\) 类和两个 \(\texttt y\) 类：也可以直接替换。

之后简单分讨一下就可以证明该命题。

那么接下来就简单了：对前 \(2k\) 个和后面 \((n-2k)\) 个分别 dp，那么「选了几个」的维度就被压缩到了 \(3\) 的长度（对于前面可以记不选了几个），那么 dp 的复杂度就降到了 \(\mathcal O(n)\)。

于是就在 \(\mathcal O(n\log n)\) 的时间复杂度内解决了本题，瓶颈在于排序。

  • 本题只有 \(x,y,z\) 三维，但实际上可以扩展到 \(m\) 维的情况。此时可以证明前面至多 \((m-1)\) 个被替换成后面的，所以可以在 \(\mathcal O(n\log n+nm^22^m)\) 的时间复杂度内解决（注意转移带一个 \(m\)）。

Code

32ms/14MB

截至现在它还是并列最优解。注意到有个 31ms 的代码与此代码编辑距离为 \(0\)。小朋友素质无敌了。

Submission link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Author: YE Minghan
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "templates/debug.h"
#else
#define dbg(...) (void)0
#define here (void)0
#endif
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=100005;
int n,k;
array<int,3>a[N];
ll dp[N][12];
void ck(ll &x,ll y){x=max(x,y);}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
	int _;cin>>_;while(_--)
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++)cin>>a[i][j];
	sort(a+1,a+n+1,[](auto x,auto y){return max({x[0],x[1],x[2]})>max({y[0],y[1],y[2]});});
	memset(dp,0xc0,8*12*(n+3));
	dp[0][0]=dp[n+1][0]=0;
	for(int i=1;i<=k<<1;i++)
		for(int j=0;j<12;j++)
		{
			ck(dp[i][j],dp[i-1][j]+a[i][0]);
			ck(dp[i][j^1],dp[i-1][j]+a[i][1]);
			ck(dp[i][j^2],dp[i-1][j]+a[i][2]);
			if(j<8)ck(dp[i][j+4],dp[i-1][j]);
		}
	for(int i=n;i>k<<1;i--)
		for(int j=0;j<12;j++)
		{
			if(j<8)ck(dp[i][j+4],dp[i+1][j]+a[i][0]);
			if(j<8)ck(dp[i][(j+4)^1],dp[i+1][j]+a[i][1]);
			if(j<8)ck(dp[i][(j+4)^2],dp[i+1][j]+a[i][2]);
			ck(dp[i][j],dp[i+1][j]);
		}
	ll ans=0;
	for(int i=0;i<12;i++)ck(ans,dp[k<<1][i]+dp[(k<<1)+1][i]),dbg(i,ans);
	cout<<ans<<endl;

}

	return 0;
}