竞赛讨论区 > T4这样可以得70分,怎么优化?难道上单调队列?
头像
王润文201903021200124
发布于 2020-11-07 17:41
+ 关注

T4这样可以得70分,怎么优化?难道上单调队列?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
ll mat[1005][1005];
ll f[1005][1005];
ll sum[1005][1005];
int main()
{
	//freopen("number.in","r",stdin);
	//freopen("number.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mat[i][j];
			f[i][j] = -99999999;
		}
	}
	f[1][1] = mat[1][1];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			sum[j][i] = sum[j-1][i]+mat[j][i];
		}
	}
	for(int i=2;i<=n;i++){
		f[i][1] = f[i-1][1]+mat[i][1];
	}
	for(int i=2;i<=m;i++){
		for(int j=1;j<=n;j++){
			f[j][i] = f[j][i-1]+mat[j][i];
			for(int k=1;k<=n;k++){
				if(k==j)continue;
				else if(k<j){
					f[j][i] = max(f[j][i],f[k][i-1]+sum[j][i]-sum[k-1][i]);
				}
				else{
					f[j][i] = max(f[j][i],f[k][i-1]+sum[k][i]-sum[j-1][i]);
				}
			}
		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}

全部评论

(5) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐