NOIP2006提高组题:能量项链,求大神指出我的代码逻辑错误
发布网友
发布时间：2022-10-16 01:40
我来回答
共1个回答
热心网友
时间：2023-10-14 11:21
你可能被题目给出的例子给误导了。题目给出的例子：
4
2 3 5 10
也就是：(2，3) (3，5) (5，10) (10，2)，最优解刚好是按顺序的，也就是
4和1，炼出的珠子再和2，接着再和3。
因此，你的程序找最优解的算法，就是枚举从任意一颗珠子开始，一直【按一个方向炼制下去】。
因为有N个珠子，因此有N中结果，你就从这个N个结果中找一个最大的，作为最优值。
但是，这个算法是不完整的！！！题目并没说一定要按给出顺序，一直炼制下去！你可以任意挑出两个珠子，只要它们的头和尾一样就可以炼制了。
因此实际的炼制方法，远远多于N。设N颗珠子有F(N)种炼制方法，则：
F(N)=N*F(N-1)，N>=3。且 F(1)=0，F(2)=1。
可以统一成：F(N)=N!/2，N>=2。F(1)=0。
题目的N范围：（4<=N<=100），如果采用暴力枚举的话，F(N)会达到很大的数量级。
你要问的，为什么：
7
23 17 212 113 71 301 33
正确结果：31182687
而我代码所产生的结果是：17489304
就是因为你枚举了N=7种情况，实际有7!/2=2520种情况，远远大于你枚举的范围。
通过上面的分析，可以知道，暴力枚举是行不通的。这题就是要用你提到的DP（动态规划来做的）。
用DP（动态规划）的做法是：
1)设有 N 颗珠子，信息保存在 pearls[N]中
2)energy[i][j] 表示从第 i 颗珠子到第 j 颗珠子能获得的最大能量，
初始设置为-1，表示还没有计算出来。
3)当 i==j ，是同一颗珠子，energy[i][j]=0
当 (i+1)%N==j，表示的是两颗相邻的珠子，能获得能量为：
energy[i][j] = pearls[i]*pearls[(i+1)%N]*pearls[(i+2)%N]
其他情况，在 i,j 之间任意选一个位置 k(i<=k<j)断开，计算：
a) 第 i 颗珠子到第 k 颗珠子的最大能量：energy[i,k]，
也就是第 k 颗珠子左边所有珠子的最大能量;
b) 第 k+1 颗珠子到第 j 颗珠子的最大能量：energy[k+1,j]，
也就是第 k 颗珠子右边所有珠子的最大能量;
c) 第k可珠子左边和右边计算能量后，各剩下一颗珠子，这两颗珠子获得的能量为：
pearls[i]*pearls[k]*pearls[(j+1)%N]
a,b,c三部分的能量相加，就是当选择 k 位置断开后，在珠子 i,j直接能获得的最大能量。
如果这个能量比原来的 energy[i][j] 要大，energy[i][j] 就更新为这个能量值。
4) energy[0][N-1]就是题目要求的，使用N颗珠子能获得的最大能量。
