[蓝桥杯][算法提高]能量项链

题目

题目链接

题解

一打眼看过去就是环形石子合并的板子题。 环形石子合并的思想就不再详述了，区间dp + 化曲为直思想

千万不要想当然地理解为就是环形石子合并稍微变了个型，代码不变。如果这么想就大错特错了。

方法一： 对应代码1

样例中的四个石子 如果直接按照石子进行合并来实现的话（见代码1）：

为四个石子编号 通过手动实现几个过程，总结出转移方程： dp[i][j]表示从第i个石子合并到第j个石子的最大花费。

dp[1][4] = max{
				dp[1][1] + dp[2][4] + stone[1].head*stone[2].head*stone[4].tail, 
				dp[1][2] + dp[3][4] + stone[1].head*stone[3].head*stone[4].tail, 
				dp[1][3] + dp[3][4] + stone[1].head*stone[4].head*stone[4].tail
			  }

好了，可以推出 dp[i][j] = max(dp[i][j], dp[i][k]+ dp[k+1][j] + stone[i].head*stone[k+1].head*stone[j].tail) k的范围：i >n; for(int i = 1;i >a[i]; for(int i = 1;i