城市牛皮癣解答 - 珍珠湾ART

公路上有2005根电线杆，它们是等距排列的，每两根之间的距离称为一个“杆距”。现在给你2005张“香港老军医”广告，分别贴在每根电线杆上。由于付给你的报酬是按你走过的杆距计算的，请设计一种走法，使得你走过的计费杆距最多，得到的报酬也最多。

计费杆距计算的规则是：从你任意选定某根电线杆贴上第一张广告算起，至你贴上最后一张广告为止。如果中间有折返点，必须在某根电线杆处折返，折返处的电线杆上要贴广告。

要求写出N根电线杆时计费杆距的最大值公式，并证明之。

好象太容易了，没人想证明。

从头上第一杆到第二杆，最多走一个来回。第二杆到第三杆，最多两个来回。依此类推，最长路程为：n=2k时为2*k^2，n=2k+1时为2*k(k+1)。但这样会形成一个环路，我们的起点和终点必须是不同的，所以要去掉一点。最少去掉1，所以最大距离是2*[(n^2)/4]-1。

具体走法是从最靠中间的一杆出发，每次走到最远一杆，然后回头。