贴广告

小张失业了，现在的工作很难找，于是小张只能选择去帮别人贴小广告。小张负责的地区有2005根电线杆，它们都是等距离排列的，每两根之间的距离称为“杆距”。

这天，小张领到了他的第一笔生意，给一家小诊所贴广告。诊所给了小张2005张广告，让他贴在他所负责的地区的每根电线杆上。

因为小张所得的报酬是按他走过的“杆距”计算的，计费杆距计算的规则是：从他任意选定某根电线杆贴上第一张广告算起，到他贴上最后一张广告为止。如果中间有折返点，必须在某根电线杆处折返，折返处的电线杆上要贴广告。那么他应该想一种什么样的走法，才能使他走过的计费“杆距”最多，从而得到的报酬也最多。你能帮他列出N根电线杆时计费杆距的最大值的公式并证明它吗？

设计费杆距为y,电线杆的数量为n，则当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。

你能明白吗？

t下！书！网 .LzuoＷen.Ｃom