城市牛皮癣

小学教育网

          
          

       
  12
                                　　公路上有2005根电线杆，它们是等距排列的，每两根之间的距离称为一个“杆距”。现在给你2005张“香港老军医”广告，分别贴在每根电线杆上。由于付给你的报酬是按你走过的杆距计算的，请设计一种走法，使得你走过的计费杆距最多，得到的报酬也最多。
　　计费杆距计算的规则是：从你任意选定某根电线杆贴上第一张广告算起，至你贴上最后一张广告为止。如果中间有折返点，必须在某根电线杆处折返，折返处的电线杆上要贴广告。
　　要求写出N根电线杆时计费杆距的最大值公式，并证明之。

点击第二页查看答案：

jzfour

       
          
          

       
  12
                               
n=0时，y=0，不用贴。n=1时，y=0，白贴，大概没人干。
不妨先做一个闭合的线路来考虑这个问题，即贴完最后一根后再回到第一根，则其行程可表示为：
y=|x1-x2|+|x2-x3|+......+|x2004-x2005|+|x2005-x1|
求y的极大值。
去掉绝对值后，y=a1-b1+a2-b2+a3-b3+.......a2005-b2005=(a1+a2+.....+a2005)-(b1+b2+......+b2005)
令这2005个点分别为1，2，3，4，......，2005
则a1+a2+a3+.....+a2005最大为2005＋2005＋2004＋2004＋2003＋......+1004+1004+1003
b1+b2+...+b2005最小为1＋1＋2＋2＋3＋3+......+1002+1002+1003
于是y的最大值为2005＋2005＋2004＋....+1004+1004+1003-1-1-2-2-......-1002-1002-1003=1003*1002*2=2010012
最后去掉闭合线路中的一条最短的：1003－1002＝1
得到答案2010011