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

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

-->1003-->1-->1004-->2-->1005-->........................1001-->2004-->1002-->2005

唉！老板赔死，暴雨累死

回大到暴雨君：

1）不对。你给出的方法并不是计费杆距的最大值。完全可能走出更多的杆距来。
2）本题要求算出计费杆距最大值的具体数。

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

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


答：暂时枚举几种想到的方法，各计算一下，取一个大数：
方法一：从1杆走起，走到底(2005)，回头，再走到底(2)，来回：
1->2005->2->2004->3->2003->...->1001->1005->1002->1004->1003
杆距和为：
2004+2003+2002+...+2+1=2004*2005/2=2009010

方法二：从1杆走起，走到1004，回头，再走到底(2)，来回：
1->1004->2->1005->3->1006->...->1001->2004->1002->2005->1003
柑橘和为：
1003+1002+1003+...+1003+1002=(1003+1002)*1002=2009010
(居然完全一样耶)


第二种方法应该和“大到暴雨”一样吧，暂时就想到两种，看来是不对了，我继续想想。

很容易知道这两种方法不对。

当N=5时，按方法一：1-5-2-4-3走有10段，按方法二：1-4-2-5-3走也是10段。但是按2-5-1-4-3走则有11段。当然我没有说N=5时11段是最大值。

对喔，奇怪，我再想想，另外看看我的13题对了没？

从边到中的方法
n=4时 2413 f(4)=2+3+2=7应该是最多
把电线杆编号以后可以形成一个排列 相邻两数字之差依次求和 就得到杆距总和
n=5 24153 f(5)=11
        
1..5这几个数字组成一个图 对所有结点一次遍历形成一条路径 线段的权值是端点数字的差 求权值最大的一条路经

线段按权值由大到小排列(相差为1)  15 (14 25) (13 24 35) (12 23 34 45)
选择15 14 52 最后从2和4任一出发到3

类似地 1--2005 1--2004 2005-2 2004--3 2--2003...1001--1004 1005--1002 1002--1003(或1004--1003)每选择一条线段 访问结点增加一个 共有2004条线段 权值分别为2004 (2003,2003) (2001,2001) (1999,1999)...(3,3) 1

相加得2005+(3+2003)*1001=2010011

这还是个贪婪算法，虽然看起来好了很多，不知道是不是最优解
这个问题用动态规划解是肯定没问题的
不过手工做很繁琐，一定要写个程序的说
或者用字典序列发生算法生成1~2500的字典序列来穷举
同样要写程序
目前想到的可以解决问题的办法
继续思考更好的方法中

[quote]原帖由[i]loranrowe[/i]于2005-07-08, 17:55:13发表
这还是个贪婪算法，虽然看起来好了很多，不知道是不是最优解
这个问题用动态规划解是肯定没问题的
不过手工做很繁琐，一定要写个程序的说
或者用字典序列发生算法生成1~2500的字典序列来穷举
同样要写程序
目前想到的可以解决问题的办法
继续思考更好的方法中 [/quote]
你把状态转移表达式列好再闪人好不好啊

[quote]原帖由[i]青木风亮[/i]于2005-07-08, 16:31:52发表
………… [/quote]
老版主又回来了？
好像才回来了一两天吧，还是多来射虎坐坐啊^_^

青木  

这个题还真不是一般的难，想了两天，还是没一点头绪。晕了，还是各位计算机专业的来解决吧。

悬赏，能用简明方法给出答案并证明的500通宝。

以某根杆子N为参照物，假设每次贴广告都经过这杆子……（先不管能否实现）
那么总行程：
|2005-N|·2+|2004-N|·2+......|1-N|·2，这个算式很容易算得N=1003时候总行程最长，为2010012

然后讨论能否实现……
N=1003时候，左边1002个来回，右边1002个来回~~来回的数目完全可以对上，也就是说每次都经过第1003根杆子是现实的，但是最后贴一个广告时，不用返回，也就是说只有来没有回，要减掉到最后的杆子第1003根杆子的距离

最后的杆子是1002号或1004号都可以，最后总行程是2010012-1
即2010011

具体跑法，1003号开始，可以任意地左右来回贴，比如（1，2005，2，2004……）最后以1002号或1004号结束即可。

英布之勇果然英勇了得。可惜功亏一篑，没证明实现的可能性（事实上是不能实现的）。

，若以1004为终点，实际上左1002个来回，右1001个来回，差一个来回可以实现的啊……即（左、右、左、右……左、1004）这样每次都经过1003，不犯规吧？

[quote]原帖由[i]英布之勇[/i]于2005-07-11, 10:09:47发表
  ，若以1004为终点，实际上左1002个来回，右1001个来回，差一个来回可以实现的啊……即（左、右、左、右……左、1004）这样每次都经过1003，不犯规吧？ [/quote]
这就是我的方法，不是最优的。

[quote]原帖由[i]英布之勇[/i]于2005-07-11, 9:59:49发表
具体跑法，1003号开始，可以任意地左右来回贴，比如（1，2005，2，2004……）最后以1002号或1004号结束即可。 [/quote]
错了，其实要少掉一个第一个的|2005-N|，因为一开始就到了1003，然后从1003开始到1也不经过，

实际上就是你的2010012-1002=2009010，那也就是我的解了。

[quote]原帖由[i]金圭子[/i]于2005-07-11, 11:58:53发表
错了，其实要少掉一个第一个的|2005-N|，因为一开始就到了1003，然后从1003开始到1也不经过，

实际上就是你的2010012-1002=2009010，那也就是我的解了。 [/quote]
还是，经过与否只能决定我的路线能否实现， 而是否往返才决定路线的长短……1003--1--1003这个往返形成，为什么要减掉1002？

我错了
简单查了一下，这个问题的一般问题，即间隔距离无特点的该问题
等价于无向图的最长路问题
是一个NP问题
基本上不可能找到通解
看来还是要找特点了，大家继续努力

你的意思是：
1003->1->2005->2->2004->3->2003->...->1001->1005->1002->1004

这样么？好像是我误解了，这样的确多一点，多处1002，就是2009010+1002=2010012

其实这个关键是第一个点和最后一个点之间的距离要尽可能小，不然就把把最后一个点放到第一个走（或者反一下），知道两个之间相隔为1，
而如果走完一个循环（就从最后一点再走一次到第一点，完成一个循环）的路程应该是一样的。

[quote]原帖由[i]金圭子[/i]于2005-07-11, 13:28:53发表
你的意思是：
1003->1->2005->2->2004->3->2003->...->1001->1005->1002->1004

这样么？好像是我误解了，这样的确多一点，多处1002，就是2009010+1002=2010012

其实这个关键是第一个点和最后一个点之间的距离要尽可能小，不然就把把最后一个点放到第一个走（或者反一下），知道两个之间相隔为1，
而如果走完一个循环（就从最后一点再走一次到第一点，完成一个循环）的路程应该是一样的。 [/quote]
我的路线长度也只有2010011……  

关于走成循环，路线应该是不一样的：（从A1开始）
循环路程S=|A1-A2|+|A2-A3|+|A3-A4|+……+|A2004-A2005|+|A2005-A1|

由于路线肯定要折返走才比较长，所以肯定上式|...|内的值必定正负交替……
S=A1-A2-A2+A3+A3-A4+...-A2004+A2005+A2005-A1
  =(A3+A5+A7+...A2005)·2-(A2+A4+A6+...A2004)·2

就是说第一根杆子被牺牲掉了，然后前半部分求最大值，后半部分求最小值

得到S=(1004+1005+...2005)·2-(1+2+3...1002)·2=2010012

若上面1004和1002调换，S值只能是2010008，可见即使是循环线路，也不是一样长的

不过根据循环也能推算出路线长度，由于循环最长到2010012（A1=1003时），然后最后去掉循环线路中的一条最短的：1（1003到1002或者是1004）

最后总路线长度的最大值是2010011

喔，我忘了减一了，我最后的1004->1003没减掉。
啊啊啊啊啊啊啊啊啊，看来我是翘鼻子，和塌鼻子无缘，老是做错 T_T