题解：AT_utpc2021_e Bounding Box

· · 题解

首先如果我们不考虑那些坐标的贡献，那就是一个十分显然的贪心。

我们首先按照价值排序，然后可以直接选择前 k 个价值最大的数，但是如果考虑坐标的贡献的话，那么我们依然可以部分贪心，我们选择前 k-4 个价值大点。

考虑后面的选择，我们设 val_{i,S}，表示在前 i 个数当中，集合 S\in\{X_{\max},X_{\min},Y_{\max},Y_{\min}\} 是否选择的贡献。

我们处理出集合的贡献之后，枚举 i,j,s，表示对于前 i 个，选了 j 个，然后集合状态为 s 的最大值，我们容易得到有 f_{j,s}。

对于当前枚举到的 i，我们考虑是否已经选择，分别考虑类似背包处理即可。

最后答案就是前面选择的和后面 dp 选择的总和统计即可。

#include <bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=2e5+10;
int val[N][17];
int f[N][17];
int n,k;
int sum;
struct E{
    int x,y,c;
    bool operator<(E a)const{
        return c>a.c;
    }
}a[N];
signed main() {
    cin>>n>>k;
    rep(i,1,n){
        cin>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+n+1);
    if(k>4){
        rep(i,1,k-4){
            sum+=a[i].c;
            a[i].c=0;
        }
    }
    rep(i,1,n){
        rep(j,0,15){
            int &v=val[i][j];
            v=a[i].c;
            if(j&1) v+=a[i].x;
            if(j&2) v-=a[i].x;
            if(j&4) v+=a[i].y;
            if(j&8) v-=a[i].y;
        }
    }
    memset(f,-0x3f,sizeof f);
    f[0][0]=0;
    rep(i,1,n){
        per(j,min({i,k,4ll}),0){
            per(s,15,0){
                for(int t=s;;t=((t-1)&s)){
                    int &v=f[j][s];
                    if(!a[i].c) v=max(v,f[j][t]+val[i][s^t]);
                    else if(j) v=max(v,f[j-1][t]+val[i][s^t]);
                    if(!t) break;
                }
            }
        }
    }
    cout<<sum+f[min(4ll,k)][15]<<'\n';
    return 0; 
}