因为每次只ban一个点 而且不是永久性的
预处理出每个点从上往下和从下往上的最大值
每次询问直接暴力 被ban掉点那行去掉那点的最大值
也可以直接预处理出每行的最大值和次大值
还有种做法貌似可以过
预处理出被ban的点是否在链上
是直接输出原本的最大的值 O(1)回答
不是暴力更新被ban的点会影响的到的那个菱形的区域 数组记录答案避免重复询问
最多这样更新n次 平均一次 n*n/4 总复杂度(n^3)/4
只要常数小+数据水就可以过了
#include<bits/stdc++.h> using namespace std; #define ll long long #define C getchar()-48 inline ll read() { ll s=0,r=1; char c=C; for(;c<0||c>9;c=C) if(c==-3) r=-1; for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c; return s*r; } #define R register const int N=1010; int n,m,ans; int a[N][N],vis[N][N],mx[N][N],b[N][N],k[N][N]; inline void work1() { for(R int i=n-1;i>=1;i--) for(R int j=1;j<=i;j++) { if(a[i+1][j]>=a[i+1][j+1]) mx[i][j]=0,a[i][j]+=a[i+1][j]; else mx[i][j]=1,a[i][j]+=a[i+1][j+1]; } for(R int i=1,j=1;i<=n;i++){vis[i][j]=1;j+=mx[i][j];} } inline void work2() { for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) b[i][j]+=max(b[i-1][j-1],b[i-1][j]); } inline int work3(int x,int y) { int ans=0; for(int i=1;i<=x;i++) { if(i==y) continue; ans=max(ans,b[x][i]+a[x][i]-k[x][i]); } return ans; } int main() { freopen("tower.in","r",stdin); freopen("tower.out","w",stdout); n=read(),m=read(); for(R int i=1;i<=n;i++) for(R int j=1;j<=i;j++) k[i][j]=a[i][j]=b[i][j]=read(); work1();work2(); for(R int i=1;i<=m;i++) { int x=read(),y=read(); if(x==1&&y==1){printf("-1 ");continue;} if(!vis[x][y]){printf("%d ",a[1][1]);continue;} printf("%d ",work3(x,y)); } return 0; }