2025年NO.2 题析-3.24初测第三题 P2096**旅游线路

科技前沿 • 2025-02-07 13:37 • 阅读 55

大家好，我是讯享网，很高兴认识大家。

某旅游区的街道成网格状。其中东西向的街道都是旅游街，南北向的街道都是林阴道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。

阿龙想到这个旅游街游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之见的街道值得游览的程度，分值是从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。如图：

输入格式

输入文件的第一行是两个整数m和n,之间用一个空格隔开，m表示有m条旅游街（1≤m≤100 ），n 表示有(n+1)条林阴道（1≤n≤20001 ）。接下来的m行依次给出了由北向南每条旅游街的分值信息。每行有n个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。

输出格式

输出文件只有一行，是一个整数，表示你的程序找到的**游览线路的总分值。

标签：贪心

难度：普及/提高-

题析

这个题屑羊在考试的时候根本没看懂题，看到至少有一个正的就枚举加正的，结果竟然拿到了10分（太奇妙辣）

10分代码（没什么用）

#include<bits/stdc++.h> using namespace std; int a[]; //不解释了考试的时候太弱智了 int main(){ int m,n,x,cnt=0; cin>>m>>n; x=m*n; for(int i=1;i<=x;i++) { cin>>a[i]; if(a[i]>0) cnt+=a[i]; } cout<<cnt; return 0; }

讯享网

考完试之后才会过味来读懂题，才发现这是一道简单的不能再简单的贪心题了~~羊の奇妙视力~~

可以理解为每一个横块后可以自由变道，所以每次找一个最大值然后加上就可以了

70分代码

讯享网#include<bits/stdc++.h> using namespace std; long long dp[20010],ans; int data[101][20010],m,n,now; long long sums; //也没有解释的必要，很简单的累加 int main(){ cin>>m>>n; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>data[i][j]; for(int j=1;j<=n;j++){ now=-99999; for(int i=1;i<=m;i++) now=max(now,data[i][j]); sums+=now; } cout<<sums; return 0; }

这个时候问题就来了，为什么只得了70？

推遍代码，样例最后一列是空的，可是程序并没有停止

这说明什么？

再看题

因为思维惯性我们会觉得这个题一定要走完

但是！并！不！是！

题目中根本就没有规定从哪里开始到那里结束

所以我们就可以只取最大段

从第一个列开始，如果两列加起来是个正数，那么证明我们所游历的是“有意义”的，反之不如不去，将起点更新成下一列

每次更新列就加到下一列里，作为下一列的起始值

AC代码

#include<bits/stdc++.h> using namespace std; long long dp[20010],ans; int data[101][20010],m,n,now; long long sums; int main(){ cin>>m>>n; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>data[i][j]; for(int j=1;j<=n;j++){ now=-99999; for(int i=1;i<=m;i++) now=max(now,data[i][j]);//mow值即当前列起始值 if(sums+now>0) sums+=now;//判定游览是否有意义 else sums=0;//无意义下移 ans=max(ans,sums); }cout<<ans; return 0; }

完awa

2025年NO.2 题析-3.24初测 第三题 P2096**旅游线路