D. X-Sum 求矩形里面斜线的和的最大值

2023-12-30 21:42:51

题目 :??https://codeforces.com/contest/1676/problem/D

思想:暴力,但是要注意很多细节,每次把当前点要走的下一步作为起点开始斜线遍历,这样可以有效避免越界问题,并且最后只用加上当前数。

代码:

// Problem: D. X-Sum
// Contest: Codeforces - Codeforces Round 790 (Div. 4)
// URL: https://codeforces.com/contest/1676/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

typedef long long ll;

const int N = 210;

int main(){
	int T;
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		int a[N][N];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		int maxv=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int ans=0;
				int x=i+1,y=j+1;
				while(x<=n&&y<=m){
					ans+=a[x][y];
					x++;
					y++;
				}
				x=i-1,y=j-1;
				while(x>=1&&y>=1){
					ans+=a[x][y];
					x--;
					y--;
				}
				x=i+1,y=j-1;
				while(x<=n&&y>=1){
					ans+=a[x][y];
					x++;
					y--;
				}
				x=i-1,y=j+1;
				while(x>=1&&y<=m){
					ans+=a[x][y];
					x--;
					y++;
				}
				ans+=a[i][j];
				
				maxv=max(maxv,ans);
			}
		}
		cout<<maxv<<"\n";
		
	}

	
	return 0;	

}

文章来源:https://blog.csdn.net/m0_73896521/article/details/135309482
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。