P8602 [蓝桥杯 2013 省 A] 大臣的旅费题目描述很久以前T 王国空前繁荣。为了更好地管理国家王国修建了大量的快速路用于连接首都和王国内的各大城市。为节省经费T 国的大臣们经过思考制定了一套优秀的修建方案使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时如果不重复经过大城市从首都到达每个大城市的方案都是唯一的。J 是 T 国重要大臣他巡查于各大城市之间体察民情。所以从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋用于存放往来城市间的路费。聪明的 J 发现如果不在某个城市停下来修整在连续行进过程中他所花的路费与他已走过的距离有关在走第x − 1 x - 1x−1千米到第x xx千米这一千米中x xx是整数他花费的路费是x 10 x10x10这么多。也就是说走1 11千米花费11 1111走2 22千米要花费23 2323。J 大臣想知道他从某一个城市出发中间不休息到达另一个城市所有可能花费的路费中最多是多少呢输入格式输入的第一行包含一个整数n ( n ≤ 10 5 ) n(n \le 10^5)n(n≤105)表示包括首都在内的T TT王国的城市数。城市从1 11开始依次编号1 11号城市为首都。接下来n − 1 n-1n−1行描述T TT国的高速路T TT国的高速路一定是n − 1 n-1n−1条。每行三个整数P i , Q , D i P_i,Q,D_iPi,Q,Di表示城市P i P_iPi和城市Q i Q_iQi之间有一条高速路长度为D i ( D i ≤ 1000 ) D_i(D_i \le 1000)Di(Di≤1000)千米。输出格式输出一个整数表示大臣J最多花费的路费是多少。输入输出样例 #1输入 #15 1 2 2 1 3 1 2 4 5 2 5 4输出 #1135说明/提示样例解释大臣 J 从城市4 44到城市5 55要花费135 135135的路费。时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛问题链接P8600 [蓝桥杯 2013 省 B] 连号区间数问题分析最值问题用枚举法会TLE。参考链接略题记略TLE的C语言程序如下/* P8600 [蓝桥杯 2013 省 B] 连号区间数 */#includeiostreamusingnamespacestd;constintN500000,INF1e8;intp[N];intmain(){intn;cinn;for(inti0;in;i)cinp[i];intcnt0;for(inti0;in;i){intmaxp-INF,minpINF;for(intji;jn;j){maxpmax(maxp,p[j]);minpmin(minp,p[j]);if(maxp-minpj-i)cnt;}}coutcnt;return0;}AC的C语言程序如下