题解P11590【[KTSC 2022 R2] 安全系统】

xuanxuan001 · 2025-02-03 10:00:43 · 题解

竟然自己做出来了，开个坑。

发现这个激光的限制很强，可以考虑给每个位置都设一个方向，然后让每个激光炮只能朝所在位置的方向射。那么发现对位置的设定限制就是这个方向上的所有其他位置都要与之相同。那么这个问题其实就是 EC-Final 2024 C 题的问题，但那题需要计数而这里只用求最值，所以不需要费脑筋地考虑算重而只需要无脑覆盖各种情况就行了~~真是太舒服了~~。

随便画一些情况，发现大概会是这个形态（NSWE 分别表示上下左右）：

NNN NSN NNE
WNN NSS NEE
WNN NSS NEE
WWW NSS EEE
WWW SSS EEE
WWS SSS SSE

观察这个 6 \times 9 的矩阵发现空格分开的三部分像是三种不同的情况。

第一种，排在最左边，从某处再分成上下两部分，上面是 W 和 N，下面是 W 和 S。
第二种，在中间，由 N 和 S 组成。
第三种，在最右边，从某处再分成上下两部分，上面是 E 和 N，下面是 E 和 S。

先预处理出每个位置被确定为某个方向后它向这个方向的这一条位置能选出的最大价值，就是一个前缀 \max。

第二种是容易的，在每一列枚举 N 和 S 的分界点即可求得。

剩下两种本质就是对某个角的子矩阵求出两种方向拼接可得的最大价值，这个可以对分界线进行 dp 得到，这条路线的方向也是确定的，将四类 dp 都求出后枚举上下分界位置即可。

求出答案就枚举两个分界线即可。

然后还有按行分开的，也就是中间有若干行由 W 和 E 组成的情况，与前面的讨论本质相同。

但当你写出来的时候会发现过不了最后一个样例，发现其实是少讨论了一类情况，比如下面这组数据：

不难发现四个炮都能被选中，答案应该是 4，但程序会输出 3。因为四个都选中的时候中间的 (2,2) 并不能选择一个合法的方向，而由于这里不放激光炮所以也无所谓，但这样的算法就不会统计这种情况。

考虑枚举被围在中间的子矩阵，然后答案用前面的 dp 值即可求出，发现这样答案对了，但 O(n^4) 的复杂度肯定不能接受。

考虑优化，但这个情况似乎很难做到 O(n^2)，本质是在矩阵中选择一个矩形，但四个角有不同的权值数组，其中隐含的左右端点的大小关系就让这个情况很难使用建图等优化。可以先枚举横坐标区间再前缀和优化做到 O(n^3)，但这个三方卡满了，似乎也难以通过。

这时考虑一些别的思路，激光炮的数量在只有 n 个，可以从这个方面入手。同时考虑这个 1500 的数据范围，如果复杂度是 n^2 的话完全可以开到 5000，带 \log 一般也会给到 2000，所以可以考虑更劣但常数小的做法。

不难发现，枚举的四个边界上必然分别有一个对应方向的被选择的炮，否则可以将这个边界缩小直到碰到一个。

那么这时就限定了要有四个方向的炮各一个，那么如果枚举不被红框框柱的三个炮，那么第四个炮的可选范围就已经被确定在那个红框内了，这似乎可以考虑一下，而枚举三个炮的复杂度不超过 (\dfrac n3)^3 = 1.25 \times 10^8，如果选择枚举次数最小的三个还可以更低，可以接受。

考虑具体做法，发现在确定了左右两个炮之后大体的形态就已经确定，可以先枚举这两个炮。然后剩下两个的横坐标区间就已确定，剩下每个炮的横坐标只要确定就可以分别确定两个区域。可以先枚举下面的炮的横坐标并求出对应情况下面的权值。然后再枚举上面的炮，这样下面的炮的横坐标范围就确定为一个后缀，直接预处理后缀和即可求得。注意不需要考虑这个范围内有没有炮，因为即使没有炮这样的一个方案也没有问题，只是会不优，前面枚举炮而非位置只是为了少枚举一些这样的不优情况以降低复杂度。

然后再将四个炮逆时针排布的情况也考虑一遍即可，与这个本质相同。

设 t_i 表示方向为 i 的炮的数量，那么复杂度就是 t_1t_2(t_3 + n)，考虑到可以旋转以选择最有情况，那么保守估计上界为 \dfrac {n^2}9 \le 4 \times 10^8，但 n 的部分完全跑不满，所以应该是可过的。而且实际上我在实现的时候根本没有旋转，最慢点应该也没超过 400ms。

代码（由于下表从 0 开始，所以所有方向值都减一）

#include<vector>
#define TY int
#define MAXN 1502
#define FOR(i,a,b) for(TY i=(a);i<=(b);i=-~i)
#define fOR(i,a,b) for(TY i=(a);i<(b);i=-~i)
#define ROF(i,a,b) for(TY i=(a);i>=(b);i=~-i)
#define rOF(i,a,b) for(TY i=(a);i>(b);i=~-i)
using namespace std;
inline TY maxn(TY a,TY b){return a>b?a:b;}
inline void updmx(TY &x,TY y){if(x<y)x=y;}
TY max_level(vector<TY> X,vector<TY> Y,vector<TY> D,vector<TY> W){
    TY n=X.size(),ar[4][MAXN][MAXN],dp[4][MAXN][MAXN],vl,mx,ans=0;
    fOR(_,0,4)FOR(i,0,n+1)FOR(j,0,n+1)ar[_][i][j]=dp[_][i][j]=0;
    fOR(i,0,n)ar[D[i]-1][X[i]][Y[i]]=W[i];
//ar 即对应方向的最大价值
    FOR(i,1,n)FOR(j,1,n){
        updmx(ar[2][i][j],ar[2][i][j-1]);
        updmx(ar[3][i][j],ar[3][i-1][j]);
    }ROF(i,n,1)ROF(j,n,1){
        updmx(ar[0][i][j],ar[0][i][j+1]);
        updmx(ar[1][i][j],ar[1][i+1][j]);
    }FOR(i,1,n){
        FOR(j,1,n)dp[0][i][j]=maxn(dp[0][i-1][j]+ar[2][i][j],dp[0][i][j-1]+ar[3][i][j]);
        ROF(j,n,1)dp[1][i][j]=maxn(dp[1][i-1][j]+ar[0][i][j],dp[1][i][j+1]+ar[3][i][j]);
    }ROF(i,n,1){
        FOR(j,1,n)dp[2][i][j]=maxn(dp[2][i+1][j]+ar[2][i][j],dp[2][i][j-1]+ar[1][i][j]);
        ROF(j,n,1)dp[3][i][j]=maxn(dp[3][i+1][j]+ar[0][i][j],dp[3][i][j+1]+ar[1][i][j]);
    }//四类 dp 值
    mx=0;FOR(i,1,n){
        FOR(j,0,n)updmx(ans,mx+dp[2][i][j]+dp[3][i][j+1]);
        FOR(j,vl=0,n)updmx(vl,ar[2][i][j]+ar[0][i][j+1]);mx+=vl;
        FOR(j,0,n)updmx(mx,dp[0][i][j]+dp[1][i][j+1]);
    }updmx(ans,mx);mx=0;FOR(j,1,n){
        FOR(i,0,n)updmx(ans,mx+dp[1][i][j]+dp[3][i+1][j]);
        FOR(i,vl=0,n)updmx(vl,ar[3][i][j]+ar[1][i+1][j]);mx+=vl;
        FOR(i,0,n)updmx(mx,dp[0][i][j]+dp[2][i+1][j]);
    }updmx(ans,mx);vector<TY>p[4];TY l,r,x,A[MAXN];
    fOR(i,0,4)p[i].clear();fOR(i,0,n)p[D[i]-1].push_back(i);
    fOR(i,0,p[0].size())fOR(j,0,p[2].size()){
        if(Y[p[0][i]]>Y[p[2][j]])continue;
        if(X[p[0][i]]+1>=X[p[2][j]])continue;
//先判掉位置关系不合法的
        l=X[p[0][i]]+1;r=X[p[2][j]]-1;
        FOR(k,l,r)A[k]=dp[0][k][Y[p[0][i]]-1]+dp[2][k+1][Y[p[2][j]]];
        ROF(k,r-1,l)updmx(A[k],A[k+1]);
//枚举两个炮并预处理第四个炮的位置情况
        fOR(k,0,p[1].size()){
            if(Y[p[1][k]]<=Y[p[2][j]])continue;
            x=X[p[1][k]];if(x<l||x>r)continue;
            updmx(ans,A[x]+dp[1][x-1][Y[p[0][i]]]+dp[3][x][Y[p[2][j]]+1]);
        }
    }fOR(i,0,p[0].size())fOR(j,0,p[2].size()){
        if(Y[p[0][i]]>Y[p[2][j]])continue;
        if(X[p[0][i]]-1<=X[p[2][j]])continue;
        l=X[p[2][j]]+1;r=X[p[0][i]]-1;
        FOR(k,l,r)A[k]=dp[1][k][Y[p[2][j]]+1]+dp[3][k+1][Y[p[0][i]]];
        ROF(k,r-1,l)updmx(A[k],A[k+1]);
        fOR(k,0,p[1].size()){
            if(Y[p[1][k]]>=Y[p[0][i]])continue;
            x=X[p[1][k]];if(x<l||x>r)continue;
            updmx(ans,A[x]+dp[0][x-1][Y[p[2][j]]]+dp[2][x][Y[p[0][i]]-1]);
        }
    }return ans;
}