在县城做团购网站,苏州做网站哪家比较好,wordpress文章编辑器插件,网页qq登录保护怎么开启某旅游区的街道成网格状。其中东西向的街道都是旅游街#xff0c;南北向的街道都是林阴道。由于游客众多#xff0c;旅游街被规定为单行道#xff0c;游客在旅游街上只能从西向东走#xff0c;在林阴道上则既可从南向北走#xff0c;也可以从北向南走。
阿龙想到这个旅游…某旅游区的街道成网格状。其中东西向的街道都是旅游街南北向的街道都是林阴道。由于游客众多旅游街被规定为单行道游客在旅游街上只能从西向东走在林阴道上则既可从南向北走也可以从北向南走。
阿龙想到这个旅游街游玩他的好友阿福给了他一些建议用分值表示所有旅游街相邻两个路口之见的街道值得游览的程度分值是从-100到100的整数所有林阴道不打分。所有分值不可能全是负分。如图 输入格式
输入文件的第一行是两个整数m和n,之间用一个空格隔开m表示有m条旅游街1≤m≤100 n 表示有(n1)条林阴道1≤n≤20001 。接下来的m行依次给出了由北向南每条旅游街的分值信息。每行有n个整数依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。
输出格式
输出文件只有一行是一个整数表示你的程序找到的最佳游览线路的总分值。
标签贪心
难度普及/提高-
题析
这个题屑羊在考试的时候根本没看懂题看到至少有一个正的就枚举加正的结果竟然拿到了10分太奇妙辣
10分代码没什么用
#includebits/stdc.h
using namespace std;
int a[2000010];
//不解释了考试的时候太弱智了
int main(){int m,n,x,cnt0;cinmn;xm*n;for(int i1;ix;i){cina[i];if(a[i]0)cnta[i];}coutcnt;return 0;
}
考完试之后才会过味来读懂题才发现这是一道简单的不能再简单的贪心题了羊の奇妙视力
可以理解为每一个横块后可以自由变道所以每次找一个最大值然后加上就可以了 70分代码
#includebits/stdc.h
using namespace std;
long long dp[20010],ans;
int data[101][20010],m,n,now;
long long sums;
//也没有解释的必要很简单的累加
int main(){
cinmn;
for(int i1;im;i)
for(int j1;jn;j)
cindata[i][j];
for(int j1;jn;j){
now-99999;
for(int i1;im;i)
nowmax(now,data[i][j]);
sumsnow;
}
coutsums;
return 0;
}
这个时候问题就来了为什么只得了70
推遍代码样例最后一列是空的可是程序并没有停止
这说明什么
再看题
因为思维惯性我们会觉得这个题一定要走完
但是并不是
题目中根本就没有规定从哪里开始到那里结束
所以我们就可以只取最大段
从第一个列开始如果两列加起来是个正数那么证明我们所游历的是“有意义”的反之不如不去将起点更新成下一列
每次更新列就加到下一列里作为下一列的起始值
AC代码
#includebits/stdc.h
using namespace std;
long long dp[20010],ans;
int data[101][20010],m,n,now;
long long sums;
int main(){
cinmn;
for(int i1;im;i)
for(int j1;jn;j)
cindata[i][j];
for(int j1;jn;j){now-99999;
for(int i1;im;i)
nowmax(now,data[i][j]);//mow值即当前列起始值
if(sumsnow0)
sumsnow;//判定游览是否有意义
else sums0;//无意义下移
ansmax(ans,sums);
}coutans;
return 0;
}
完awa
