Loading... ## 题目 *题目有修改* ### 描述 在一串项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。对于相邻的两颗珠子，前一颗珠子的尾标记等于后一颗珠子的头标记。设前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 m× r × n，新产生的珠子的头标记为 m，尾标记为 n。 我们可以通过聚合相邻的两颗珠子得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的。请你设计一个聚合顺序，使一串项链释放出的总能量最大。 ### 输入 输入第一行是一个正整数 N（4≤N≤100），表示项链上珠子的个数。 第二行是 N 个用空格隔开的正整数，所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记（1≤i≤N），当 i<N 时，第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N颗珠子的尾标记应该等于第 1 颗珠子的头标记。 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 ### 输出 输出只有一行，是一个正整数E（E≤2.1*10^9109），为一个最优聚合顺序所释放的总能量。 ## 题解 这是一个经典的区间DP问题。 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://www.coco07.com/index.php/76.html" target="_blank" class="post_inser_a no-external-link"> <div class="inner-image bg" style="background-image: url(https://coco07.com/usr/uploads/2020/07/2747507733.png);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">区间DP</p> <div class="inster-summary text-muted"> 区间DP属于线性DP的一种，它以“区间长度”作为DP的“阶段”，使用两个坐标（区间的左、右端点）描述每个维度。在区... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> 以k为分割点将一个区间（一串项链）分割（聚合相邻两个珠子）成两个个小区间（两串项链），这样的分割操作示意图如下。  图中清晰地呈现了一串项链的聚合过程以及聚合过程中每颗珠子头尾标记的变化。进行一次聚合操作得到的能量为a[l]*a[k+1]*a[r+1]。 ## 代码 ``` #include <cstdio> #include <algorithm> using namespace std; int n, a[200]; long long f[200][200]; long long dp(int l, int r){ if(f[l][r]) return f[l][r]; if(l == r) return 0; f[l][r] = 0; for(int k = l; k < r; ++k){ f[l][r] = max(f[l][r], dp(l, k)+dp(k+1, r)+a[l]*a[k+1]*a[r+1]); } return f[l][r]; } int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%d", &a[i]); a[i+n] = a[i]; } long long ans = 0; for(int i = 0; i < n; ++i){ ans = max(ans, dp(i, i+n-1)); } printf("%lld\n", ans); return 0; } ``` © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
