序列最小值问题

lzlxm

<>问对于一个序列P1,P2,...,Pn,求一种排序使得</P>
<><FONT size=5>S=∑∑Pi*Pj(j-i) (1&lt;=i&lt;j&lt;=n)</FONT></P>
<>最小</P>
<P>这是有2个<FONT size=5>∑</FONT>，其中i=1,2,...,n-1, j=i+1,....,n</P>
<P>是否能给出算法和证明？</P>
<P><FONT size=5></FONT> </P>

lzlxm

<>我举个例子，比如有序列 1,2,3</P><>当排序为1,2,3时</P><>S=1*2+1*3*2+2*3=14</P><P>当排序为1,3,2时</P><P>S=1*3+1*2*2+3*2=13</P><P>所以1,3,2比1,2,3经过计算后小</P><P>有几个我发现的规律分享一下，序列是对称的，1,2,3算出来和3,2,1结果是一样的</P><P>大的要放在中间，小的放两边，但有相互影响</P>

lzlxm

<>没人顶呀？太失望了...</P>

lzlxm

<>晕，莫非此题只能用穷举法？还是太难了？</P>

knight

<>你考虑过用置换群的方法吗？</P>

lzlxm

置换群的方法我没用过，我这几天看一下资料，如果我证明出来了也会贴在这边

knight

<>你的每一个序列是原来一个序列的置换。你无非是要找一个最佳的置换，置换分为偶置换和奇置换，n个元素的集合上的所有置换对于置换的乘法可以做成一个群，叫n次对称群Sn。Sn是可以用两个置换生成，分别是一个轮换和一个对换。把你的目标放到Sn中去求最优我觉得会比较容易找到。</P>