前置芝士：状压 dp。
题目大意
给定平面上 \(n\) 个点及其代价。Alice 可删除部分点（可为空但不能全部删除），Bob 绘制包含剩余点的最小轴平行矩形（可退化为线段或点）。得分等于 Alice 删除点的代价之和加上矩形的周长。Alice 旨在最大化得分，Bob 旨在最小化得分。求两人均最优时的最终得分。
思路
我们来观察一些结论：
- 首先 Bob 的选择策略是唯一的，就是全部压着边框选，那么就是选最高最矮的两条长和最两边的两条宽，我们只需要知道四边的坐标就可以知道 Bob 的答案。
- Alice 选择时，没有对边框产生影响的点完全可以删去，显然最后只会有边框上的最多四个点，因为一个点可以同时划定多个边框，所以最后可能不满四个点。
观察到这些之后，因为 Bob 策略已知，我们不妨直接带入 Alice 的视角，在计算的时候直接算掉 Bob 的贡献。设 \(f_{i,S}\) 为选到第 \(i\) 个点，上/下/坐/右的点选/没选的最大值，\(w_{i,S}\) 为第 \(i\) 个点，上/下/坐/右的点是/不是边框的权值，那么我们有：
\[f_{i,S}=\left\{\begin{matrix} f_{i-1,S}+c_i \\ \max_{S'\in S} f_{i-1,S'}+2\times w_{i,S1\setminus S2} \end{matrix}\right.
\]
点击查看代码
https://codeforces.com/contest/2169/submission/349375322
#include<bits/stdc++.h>#define int ll
#define pii pair<int,int>
#define pll pair<long long,long long>
#define ll long long
#define i128 __int128#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first
#define scd second
#define dbg puts("IAKIOI")using namespace std;int read() {int x=0,f=1; char c=getchar();for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }const int maxn = 300050;
const int maxS = (1<<4)-1;int n,a[3][maxn];
int w[maxn][maxS+1];
int f[maxn][maxS+1];void work() {in1(n);For(qwq,0,2) For(i,1,n) in1(a[qwq][i]);For(i,1,n) For(S,0,maxS) {w[i][S]=0;For(j,0,3) if((S>>j)&1) {w[i][S]+=a[j&1][i]*(j<2?-1:1);}
// cout<<i<<' '<<S<<' '<<w[i][S]<<'\n';}For(i,0,n) For(S,0,maxS) f[i][S]=-4e18;f[0][0]=0;For(i,1,n) For(S1,0,maxS) {f[i][S1]=f[i-1][S1]+a[2][i];for(int S2=S1;;S2=(S2-1)&S1) {f[i][S1]=max(f[i][S1],f[i-1][S2]+2*w[i][S1^S2]);if(S2==0) break;}}cout<<f[n][maxS]<<'\n';
}signed main() {
// freopen("data.in","r",stdin);
// freopen("myans.out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);double stt=clock();int _=1;_=read();
// cin>>_;For(i,1,_) {work();}cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';return 0;
}