竖直方向可以随便走嘛，所以求出每一列 的最大值，再做比较就可以了(求最大子段和)。
ACcode:
文章来源：https://www.toymoban.com/news/detail-611608.html
#include<bits/stdc++.h>
using namespace std;
int n,m,a[105][20010],b[20010],dp[20010];
void solve() {
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int j=1;j<=m;j++){
int mmax=-1<<30;
for(int i=1;i<=n;i++){
mmax=max(mmax,a[i][j]);
}
b[j]=mmax;
}
int ans=-1<<30;
for(int i=1;i<=m;i++){
dp[i]=max(dp[i],dp[i-1]+b[i]);
ans=max(ans,dp[i]);
}
cout<<ans<<"\n";
}
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int tt=1;
//cin>>tt;
while(tt--)
solve();
return 0;
}
over~文章来源地址https://www.toymoban.com/news/detail-611608.html
到了这里，关于P2096 最佳旅游线路的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
