【简】题解 AWSL090429 【数塔问题】

因为每次只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=,r=;

    char c=C;

    for(;c<||c>;c=C) if(c==-) r=-;

    for(;c>=&&c<=;c=C) s=(s<<)+(s<<)+c;

    return s*r;

}

#define R register

const int N=;

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-;i>=;i--)

    for(R int j=;j<=i;j++)

    {

        if(a[i+][j]>=a[i+][j+]) mx[i][j]=,a[i][j]+=a[i+][j];

        else mx[i][j]=,a[i][j]+=a[i+][j+];

    }

    for(R int i=,j=;i<=n;i++){vis[i][j]=;j+=mx[i][j];}

}

inline void work2()

{

    for(int i=;i<=n;i++)

    for(int j=;j<=i;j++)

      b[i][j]+=max(b[i-][j-],b[i-][j]);

}

inline int work3(int x,int y)

{

    int ans=;

    for(int i=;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=;i<=n;i++)

    for(R int j=;j<=i;j++)

      k[i][j]=a[i][j]=b[i][j]=read();

    work1();work2();

    for(R int i=;i<=m;i++)

    {

        int x=read(),y=read();

        if(x==&&y==){printf("-1\n");continue;}

        if(!vis[x][y]){printf("%d\n",a[][]);continue;}

        printf("%d\n",work3(x,y));

    }

    return ;

}