AT_abc400_g [ABC400G] Patisserie ABC 3 题解

· · 题解

调的有点久。

如果不考虑 k 的限制，那么有一个显然的 DP：先把 x,y,z 的贡献拆掉，转化成选一些数两两配对，计算他们 x_i 的贡献；再选另外一些数配对，计算他们 y_i 的贡献；对 z_i 同理。

又由于他们可以任意配对，所以限制就可以直接写成：

从序列中选出三组数，其中每一组的数量都是偶数。答案是第一组的 x_i 之和加上第二组的 y_i 之和加上第三组的 z_i 之和。

这样是对的，因为错解一定是不优的。

DP 的时候直接多记一维状态 0 \le S < 2^3 表示三组数个数的奇偶性即可。单次时间复杂度 O(n)。

现在加上 k 的限制。我们发现选 k 组的答案关于 k 是凸的（理解一下就是一定会先选出贡献大的数对，斜率是不增的）。直接上 wqs 二分就行。

写的时候注意一下二分的是 x 到 x+2 之间的斜率，要进行一些乘除 2 的处理，具体看代码吧。

#include<bits/stdc++.h>
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
    int ch=getchar();
    T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=f;rd(args...);
}
const int N=1e5+5;
typedef long long ll;
const ll INF=1e18;
int T,n,k,v[N][3];
std::pair<ll,int> dp[N][8];
inline std::pair<ll,int> Solve(int x){
    for(int i=0;i<8;i++)dp[0][i]={-INF,0};
    dp[0][0]={0,0};
    for(int i=1;i<=n;i++){
        for(int j=0;j<8;j++){
            dp[i][j]=dp[i-1][j];
            for(int k=0;k<3;k++){
                auto tmp=std::make_pair(dp[i-1][j^(1<<k)].first+2*v[i][k]-x,dp[i-1][j^(1<<k)].second+1);
                dp[i][j]=std::max(dp[i][j],tmp);
            }
        }
    }return dp[n][0];
}
inline void Solve(){
    rd(n,k);
    for(int i=1;i<=n;i++)rd(v[i][0],v[i][1],v[i][2]);
    int L=0,R=2e9;
    while(L<=R){
        int mid=(0ll+L+R)>>1;
        Solve(mid);
        if(dp[n][0].second>=2*k)L=mid+1;
        else R=mid-1;
    }
    Solve(R);
    printf("%lld\n",dp[n][0].first/2+1ll*k*R);
}
signed main(){
    rd(T);
    while(T--)Solve();
    return 0;
}