博客破百祭！！！

题目链接

https://www.luogu.com.cn/problem/P1063

解题思路

一道十分类似的题
成环已经不是难点了吧，化环为链。
与上面那个题不同的是这个题两个数也可以操作，因为是俩珠子，形如珠子1(10,2) 珠子2(10,2)，最大的得分为10*2*10=200 > 2*10*2=40，显然上面那个题只能对至少三个珠子操作吧。
dp的含义依旧是取走i，j之间的全部数，得到的最大值。
本质上的区别在于本题可以取数取到只剩一个数，那我们把最长区间取到长度为n+1，最后输出长度为n+1的区间中的最大值，而且最小区间长度可以为2。
当区间长度取到n+1的时候，a[i]==a[j]，这就相当于实现了取到只剩一个数的操作，
举个例子：10 3 2 10 3 2，i=1,j=4时，相当于把3留下与两端的10合并，或者把2留下与两端的10合并，最后相当于就剩了个10。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110;
ll dp[N<<1][N<<1],a[N<<1],n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }

    for(int len=2;len<=n+1;len++)//注意范围
        for(int i=1;i+len-1<=n+n;i++){
            int j=len+i-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]);
        }

    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i][i+n]);//注意dp的第二维

    cout<<ans<<endl;
}