Time Limit: 2s Memory Limit: 192MB
Problem Description
On the planet Mars, every Martian carries a string of energy necklaces. Each necklace contains N energy beads. An energy bead has a head marker and a tail marker, which correspond to a positive integer. Moreover, for two adjacent beads, the tail marker of the previous bead must equal the head marker of the next bead. Only in this way can these two beads merge into one bead through the action of a suction cup (a Martian organ for absorbing energy), simultaneously releasing energy that can be absorbed by the suction cup. If the head marker of the previous energy bead is m, the tail marker is r, the head marker of the next energy bead is r, and the tail marker is n, then the energy released upon merging is m*r*n (in Martian units), and the new bead’s head marker is m, and the tail marker is n.
When needed, Martians use the suction cup to grasp two adjacent beads, merging them to obtain energy until only one bead remains on the necklace. Clearly, the total energy obtained from different merging sequences is different. Please design a merging sequence that maximizes the total energy released by a string of necklaces.
For example: Let N=4, the head and tail markers of the 4 beads are (2,3), (3,5), (5,10), (10,2) respectively. We use the symbol ◎ to indicate the merging operation of two beads, where (j◎k) indicates the energy released after merging the j-th and k-th beads. The energy released by merging the 4th and 1st beads is:
(4◎1)=10*2*3=60.
The total energy released by an optimal merging sequence for this string of necklaces is
((4◎1)◎2)◎3)=10*2*3+10*3*5+10*5*10=710.
Input Format
The first line is a positive integer N (4≤N≤100), indicating the number of beads on the necklace. The second line contains N positive integers separated by spaces, all of which do not exceed 1000. The i-th number is the head marker of the i-th bead (1≤i≤N), and when i<n, (i+1)-th="" 1st="" bead="" bead.="" bead.
As for the order of the beads, you can determine it as follows: place the necklace on the table without crossing, arbitrarily designate the first bead, and then determine the order of the other beads in a clockwise direction.
Output Format
Only one line, which is a positive integer E (E≤2.1*10^9), representing the total energy released by an optimal merging sequence.
Sample Input
4
2 3 5 10
Sample Output
710
Code
#include <iostream>#include <vector>#include <algorithm>using namespace std;
int main() { int n; cin >> n;
vector<int> a(2 * n); for (int i = 0; i < n; i++) { cin >> a[i]; a[i + n] = a[i]; // Copy a second time }
vector<vector<int>> dp(2 * n, vector<int>(2 * n, 0));
// Interval DP for (int len = 2; len <= n; len++) { // Interval length from 2 to n for (int i = 0; i + len - 1 < 2 * n; i++) { int j = i + len - 1; for (int k = i; k < j; k++) { // Merge [i,k] and [k+1,j] dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + a[i] * a[k+1] * a[j+1]); } } }
// Find the maximum value in a circular manner int maxEnergy = 0; for (int i = 0; i < n; i++) { maxEnergy = max(maxEnergy, dp[i][i + n - 1]); }
cout << maxEnergy << endl;
return 0;}Output Result
Code Explanation
-
Input Handling
-
Read the number of beads
<span>n</span> -
Read
<span>n</span>head markers and copy a second time to form a<span>2n</span>length array
DP Array Initialization
-
<span>dp[i][j]</span>initialized to 0
Interval DP Calculation
-
Calculate by interval length from small to large
-
For each interval
<span>[i, j]</span>, enumerate the split point<span>k</span> -
State Transition:
<span>dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + a[i] * a[k+1] * a[j+1])</span>
Circular Maximum Value
-
Traverse all possible starting points to find the maximum energy value of the interval of length
<span>n</span>
This is a classic circular interval DP problem, similar to the circular version of matrix chain multiplication.
Problem Analysis
-
Circular ProcessingThe necklace is circular, so we need to copy the array a second time, making it a length of
<span>2n</span>array, and then perform interval DP on this linear array. -
State DefinitionLet
<span>dp[i][j]</span>represent the maximum energy released when merging from the i-th bead to the j-th bead into one bead. -
State TransitionFor the interval
<span>[i, j]</span>, we enumerate the last merge position<span>k</span>(<span>i ≤ k < j</span>), dividing the interval into<span>[i, k]</span>and<span>[k+1, j]</span>two parts.The energy released by merging these two parts is:dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + a[i] * a[k+1] * a[j+1])Here,
<span>a[i]</span>is the head marker of the i-th bead,<span>a[i+1]</span>is its tail marker (which is also the head marker of the next bead). -
State Transition
We enumerate the starting point of the circle <span>start</span> (<span>0 ≤ start < n</span>), calculate the maximum energy of the interval of length <span>n</span> starting from <span>start</span>, and take the maximum value.
C++ Basic Tutorial Collection
C++ Basic Materials
1. C++ Output
2. C++ Variables
3. C++ Input
4. C++ Expressions
5. IF Statement
6. IF Applications
7. WHILE Loop Statement
8. FOR Loop Statement
9. Arrays
10. One-Dimensional Arrays
11. Two-Dimensional Arrays
12. C++ Functions
13. C++ File Operations – Write File Operations
If you find it interesting, just click on me
