建议删除标签

P1719 最大加权矩形

zhengyi0402 @ 2024-12-29 20:11:54

建议删除除前缀和以外的标签。

(下面的代码不就过了吗?)

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3fll
#define atn 222222
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int a[222][222],s[222][222];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;j++){
            cin>>a[i][j];
        }
    }
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    int ans = -inf;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;j++){
            for(int k = i+1;k <= n;k++){
                for(int l = j+1;l <= n;l++){
                    ans=max(s[k][l]-s[i-1][l]-s[k][j-1]+s[i-1][j-1],ans);
                }
            }
        }
    }cout<<ans<<endl;
    return 0;
    //十年OI一场空,define int 见祖宗。
    //十年OI一场空,不开long long见祖宗。
}

也不需要降维,DP 鸭


|