题解：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 选择的总和统计即可。

CPP

#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; 
}

题解：AT_utpc2021_e Bounding Box

文章操作

相关推荐

评论

题解：AT_utpc2021_e Bounding Box