[已解决]求助

叼辣条闯世界

如图

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2022-8-28 19:40:41

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. long long sum[12][12];
   
5. int mp[12][12];
   
6. int n;
   
7. long long maxpart = LONG_LONG_MIN;
   
8. double ans;
   
9. 
   
10. int main(){
    
11.     ios::sync_with_stdio(0);
    
12.     cin.tie(0); cout.tie(0);
    
13.    
    
14.     cin >> n;
    
15.     for(int i = 1; i <= n; i++){
    
16.         for(int j = 1; j <= n; j++){
    
17.             cin >> mp[i][j];
    
18.             sum[i][j] = sum[i-1][j] + mp[i][j]; // 列的前缀和
    
19.         }
    
20.     }
    
21. 
    
22.     for(int j = 1; j <= n-1; j++){
    
23.         for(int i = 1; i <= n-1; i++){
    
24.             maxpart = max(maxpart, sum[i+1][j]-sum[i-1][j] + sum[i+1][j+1]-sum[i-1][j+1]);
    
25.         }
    
26.     }
    
27. 
    
28.     ans = (double)maxpart / 4;
    
29. 
    
30.     cout << fixed << setprecision(2) << ans << endl;
    
31.    
    
32.     return 0;
    
33. }
    
34. 
    
35. /* 你的样例
    
36. 3
    
37. 1 2 3
    
38. 2 3 4
    
39. 3 4 5
    
40. */

复制代码

跳转到最佳答案楼层

柿子饼同学

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. long long sum[12][12];
   
5. int mp[12][12];
   
6. int n;
   
7. long long maxpart = LONG_LONG_MIN;
   
8. double ans;
   
9. 
   
10. int main(){
    
11.     ios::sync_with_stdio(0);
    
12.     cin.tie(0); cout.tie(0);
    
13.    
    
14.     cin >> n;
    
15.     for(int i = 1; i <= n; i++){
    
16.         for(int j = 1; j <= n; j++){
    
17.             cin >> mp[i][j];
    
18.             sum[i][j] = sum[i-1][j] + mp[i][j]; // 列的前缀和
    
19.         }
    
20.     }
    
21. 
    
22.     for(int j = 1; j <= n-1; j++){
    
23.         for(int i = 1; i <= n-1; i++){
    
24.             maxpart = max(maxpart, sum[i+1][j]-sum[i-1][j] + sum[i+1][j+1]-sum[i-1][j+1]);
    
25.         }
    
26.     }
    
27. 
    
28.     ans = (double)maxpart / 4;
    
29. 
    
30.     cout << fixed << setprecision(2) << ans << endl;
    
31.    
    
32.     return 0;
    
33. }
    
34. 
    
35. /* 你的样例
    
36. 3
    
37. 1 2 3
    
38. 2 3 4
    
39. 3 4 5
    
40. */

复制代码