P2096 最佳旅游线路

最大字段和加贪心

算长了个见识吧

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

long long map[210][20010];

int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			scanf("%lld",&map[i][j]);

	long long ha=0,now,ans=0;

	for(int i=1;i<=m;i++)

	{

		now=-1000000;

		for(int j=1;j<=n;j++)

			now=max(map[j][i],now);

		ans=max(ans,ha);

		ha+=now;

		if(ha<0)

			ha=0;

	}

	ans=max(ans,ha);

	printf("%lld",ans);

}

巴特西

P2096 最佳旅游线路

最新文章

热门文章