题解：CF2169E Points Selection

· · 题解

本题体现了非法情况不优，则可以不管非法情况的思想，该思想可以用这道例题入门。为了便于不了解该思想的选手阅读题解，本题解先讲做法，再说正确性。

做法

按照题意，保留的点下标组成集合 A、删除的点下标组成集合 B，则总分的表达式\displaystyle 2(x_{mx1}-x_{mn1}+y_{mx2}-y_{mn2})+\sum_{i\in B} c_i，之中 mx1,mx2,mn1,mn2\in A 表示 A 中点在对应坐标维度的最大或最小值。前面周长项就是 Bob 能做到的最短周长，所以下面就没有 Bob 的事情了，站在 Aliec 角度最大化这个式子即可。

反过来考虑每个点对答案的贡献，发现贡献可能是：

还有别的可能吗？再仔细一想，如果一个点作为保留点的最右下角，其贡献是 2x_i-2y_i，甚至如果一个点是唯一保留的点，其贡献会是 2x_i-2x_i+2y_i-2y_i=0，注意这对应了不能把所有点删光所以必须留一个点的可能。但总之，我们发现贡献的情况很多，于是考虑用四位二进制数来描述一个点的贡献：该二进制数低位到高位的二进制位为 1 分别表示有 2x_i,-2x_i,2y_i,-2y_i 的贡献，特别地，c_i=0 表示贡献为 c_i。

还有什么限制？我们发现在计算周长时，x_{mx},x_{mn},y_{mx},y_{mn} 都只能被一个 i 来贡献，不然比如让多个点贡献 x_{mx} 会导致答案错误的变大。为了解决这个问题，定义 dp_{i,j} 表示前 i 个点，当前四项已经被贡献的情况（四位二进制数）为 j，转移时枚举四位二进制数 k 满足 j\&k=0，用于更新 dp_{i+1,j\oplus k}，从而确保每个位置只会被贡献一次，最终答案是 dp_{n,15}。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,xx[300010],yy[300010],c[300010],dp[300010][16];
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)   cin>>xx[i];
        for(int i=1;i<=n;i++)   cin>>yy[i];
        for(int i=1;i<=n;i++)   cin>>c[i];
        for(int i=0;i<=n+5;i++){
            for(int j=0;j<16;j++)   dp[i][j]=-1e18;
        }
        dp[0][0]=0;
        for(int i=0;i<=n-1;i++){
            for(int j=0;j<16;j++){
                for(int k=0;k<16;k++){
                    if(k&j) continue;
                    ll tmp=0;
                    if(k&(1<<0))    tmp+=2*xx[i+1];
                    if(k&(1<<1))    tmp-=2*xx[i+1];
                    if(k&(1<<2))    tmp+=2*yy[i+1];
                    if(k&(1<<3))    tmp-=2*yy[i+1];
                    if(!k)  tmp=c[i+1];
                    dp[i+1][j|k]=max(dp[i+1][j|k],dp[i][j]+tmp); 
                }
            }
        }
        cout<<dp[n][15]<<"\n";
    }
    return 0;
}

正确性

刚刚的 DP 有一些看上去显而易见的问题：

DP 里只确保了 x_{mx},x_{mn},y_{mx},y_{mn} 被贡献恰好一次，完全没检验集合 A 中是否是用最大横坐标点来贡献 x_{mx}、最小横坐标点来更新 x_{mn}......这对吗？

答：这就是我们提到的“非法情况不优，则可以不管非法情况”思想，即如果 x_{mx} 不是用集合 A 中最大项来贡献的、把 A 中最大项换为 x_{mx} 的方案一定更优且也会被我们的 DP 考虑。

类似的，DP 中会考虑包括三项的贡献式子也是如果非法一定不优的、所以可以考虑。