[已解决]求助

叼辣条闯世界

如图

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2022-8-28 19:40:41

这个数据量很小了, 范围又是确定的, 直接暴力都可以, 这个是 O(n^2), 暴力好像就常数大一点
建议自己先思考再来问
不过用前缀和优化了一下下
还有, 下次测试样例打字上来吧

#include <bits/stdc++.h>
using namespace std;

long long sum[12][12];
int mp[12][12];
int n;
long long maxpart = LONG_LONG_MIN;
double ans;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> mp[i][j];
            sum[i][j] = sum[i-1][j] + mp[i][j]; // 列的前缀和
        }
    }

    for(int j = 1; j <= n-1; j++){
        for(int i = 1; i <= n-1; i++){
            maxpart = max(maxpart, sum[i+1][j]-sum[i-1][j] + sum[i+1][j+1]-sum[i-1][j+1]);
        }
    }

    ans = (double)maxpart / 4;

    cout << fixed << setprecision(2) << ans << endl;
    
    return 0;
}

/* 你的样例
3
1 2 3
2 3 4
3 4 5
*/

跳转到最佳答案楼层

柿子饼同学

这个数据量很小了, 范围又是确定的, 直接暴力都可以, 这个是 O(n^2), 暴力好像就常数大一点
建议自己先思考再来问
不过用前缀和优化了一下下
还有, 下次测试样例打字上来吧

#include <bits/stdc++.h>
using namespace std;

long long sum[12][12];
int mp[12][12];
int n;
long long maxpart = LONG_LONG_MIN;
double ans;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> mp[i][j];
            sum[i][j] = sum[i-1][j] + mp[i][j]; // 列的前缀和
        }
    }

    for(int j = 1; j <= n-1; j++){
        for(int i = 1; i <= n-1; i++){
            maxpart = max(maxpart, sum[i+1][j]-sum[i-1][j] + sum[i+1][j+1]-sum[i-1][j+1]);
        }
    }

    ans = (double)maxpart / 4;

    cout << fixed << setprecision(2) << ans << endl;
    
    return 0;
}

/* 你的样例
3
1 2 3
2 3 4
3 4 5
*/