题解 P2096 【最佳旅游线路】

据说此题的最大坑点就是读入时间，于是我就把读入优化放了出来。**此读入优化并不是最佳读入优化，但是对P党友好，而且在C++下还可以自动防止因数据输入不完整或因linux换行符或文件读入有空格而造成的RE、TLE等**（WA就不保证了）（如果要达到拓展功能，请勿修改while循环部分），并且还可以吃掉下一个字符来达到readln（换行）的效果。读入优化+DP=3ms ```cpp #include<bits/stdc++.h> using namespace std; int road[20001]; inline int read(){ int num=0;//初始化整数 char c,sf=1;//字符、负数标记 while(isspace(c=getchar()));//核心语句 if(c=='-') sf=-1,c=getchar();//判断负数 while((num=num*10+c-48)&&isdigit(c=getchar())); return num*sf; } int main(){ int m=read(),n=read(),temp1; memset(road,128,sizeof(road));//可以初始化为最小整数 for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ temp1=read(); if(temp1>road[j]) road[j]=temp1;//只取当前这一列最大值 ``` }//因为允许南北向走而无花费，所以每一列可以选最大值 }//其实题意是人可以从任意一列进去，从任意一列出来（看了半天） int max\_v=-536870912,now\_v=0;//初始化，记录最大值和当前值 ```cpp for(int i=1;i<=n;i++){ if((temp1=road[i]+now_v)>max_v) max_v=temp1;//temp1减少加法次数，一直寻找字段最大值 if(temp1<0) now_v=0;//如果前面部分小于0就没有贡献且“拖后腿”（就舍去） else now_v=temp1;//否则继续累加 } printf("%d",max_v); return 0; } ```