320. Energy Necklace (ring, interval DP)

 320. Energy necklace - AcWing Question bank

analysis ： It can be regarded as a circular interval dp problem

Altogether 4 A bead , There are four marks as shown in the figure , It can be merged to the end, leaving only 2 A sign , That is to say 1 A bead .

Then at least it needs 3 Tags can continue to merge , If it is less than three tags, there is no need to merge .

State means ： All consolidation i~j A collection of tags

State calculation / Basis of division ： according to i~j The marks in the middle can be divided into those that are neither heavy nor missing j-i-1 A collection of , because i,j It means the mark , Therefore, you cannot participate in the merger (dp[i][i] Not a bead , Do not participate in the operation , therefore dp[i][j],j>=i+1)

The recurrence formula is dp[i][k]+dp[k][j], Because the set before the breakpoint k As a tail mark , The latter set k As a header mark

• i+1 As a breakpoint , Merge dp[i][i+1],dp[i+1][j],dp[i][j]=dp[i][i+1]+dp[i+1][j]+w[i]*w[i+1]*w[j]
• ...
• j-1 As a breakpoint , Merge dp[i][j-1],dp[j-1][j],dp[i][j]=dp[i][j-1]+dp[j-1][j]+w[i]*w[j-1]*w[j]

Initialization and boundary are 0

Recursive method ：

for(int len=1;len<=n+1;len++)// Because the right endpoint may be the starting point , therefore <=n+1
// Because the tail mark of the last bead is the first mark 
        for(int i=1;i+len-1<=2*n;i++)
        {
            ...
        }

ac Code

#include <iostream>
#include <algorithm>
using namespace std;
const int N=205;
const int INF=0x3f3f3f3f;
int a[N];
int s[N];
int dp[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],a[n+i]=a[i];
    
    for(int len=1;len<=n+1;len++)
        for(int i=1;i+len-1<=2*n;i++)
        {
            int j=i+len-1;
            for(int k=i+1;k<j;k++)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
        }
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,dp[i][i+n]);
    cout<<res;
}