题目链接


一道水体,很显然需要二维前缀和,然后考虑一个$O(n^2)$算法,枚举每一个点作为炸弹投放矩阵的右下角,这题就做完了qwq。

代码如下

    #include<bits/stdc++.h>
    using namespace std;
    const int N=5009;
    int a[N][N],ans;
    int main(){
        int n,r;
        cin>>n>>r;
        for(int i=1;i<=n;i++){
            long long x,y,z;
            cin>>x>>y>>z;
            a[x+1][y+1]=z;
        }
        for(int i=1;i<=5001;i++){
            for(int j=1;j<=5001;j++){
                a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            }
        }
        for(int i=r;i<=5001;i++){
            for(int j=r;j<=5001;j++){
                ans=max(ans,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);
            }
        }
        if(ans==0) return 0;
        cout<<ans;
        return 0;
    }

P.S.绿题难度怎么差异这么大,~也太简单了吧!~

Last modification:March 14th, 2020 at 08:50 pm