【区间dp 环形dp】洛谷_1063 能量项链

本文主要是介绍【区间dp 环形dp】洛谷_1063 能量项链，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出$N$个珠子，每个珠子有头和尾，我们每次让两颗珠子聚合，得到的能量就是（第一颗珠子的头$\times$第一颗珠子的尾$\times$第二个珠子的尾），聚合后，得到新珠子，头为第一颗珠子的头，尾为第二颗珠子的尾。
这些珠子连成一个环，求出一个聚合顺序使得得到的能量最大。

思路

区间的动态规划。
我们设$f[i][j]$为第$i$颗珠子聚合到第$j$颗珠子的最大值，可得出动态转移方程：
$f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]\times a[k+1]\times a[j+1])$
其中 k k <script type="math/tex" id="MathJax-Element-472">k</script>为枚举的断点，处理环形我们就把给出的数据复制两倍然后再做。

代码

#include<cstdio>
#include<algorithm>
using namespace std;int N, ans;
int F[401][401], a[201];int main() {scanf("%d", &N);for (int i = 1; i <= N; i++) {scanf("%d", &a[i]);a[i + N] = a[i];}for (int i = 2 * N; i >= 1; i--)for (int j = i; j - i < N && j <= 2 * N; j++)for (int k = i; k < j; k++) {F[i][j] = max(F[i][j], F[i][k] + F[k + 1][j] + a[i] * a[k + 1] * a[j + 1]);ans = max(ans, F[i][j]);}printf("%d", ans);
}

这篇关于【区间dp 环形dp】洛谷_1063 能量项链的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---