题目描述

状态计算
以分界线来划分矩阵l+1,l+2…r-2,r-1，
分界线k从l+1开始枚举
区间长度不是n，是n+1

#include <iostream>
#include <cstring>

//状态计算
//以分界线来划分矩阵l+1,l+2...r-2,r-1

using namespace std;

const int N=210;
int n;
int w[N];
int f[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i+n]=w[i];
    }
    for(int len=3;len<=n+1;len++)
    {
        for(int i=1;i+len-1<=n*2;i++)
        {
            int j=i+len-1;
            //枚举分界线,从i+1开始枚举
            for(int k=i+1;k<j;k++)
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]+w[i]*w[j]*w[k]);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    res=max(res,f[i][i+n]);

    cout<<res<<endl;

    return 0;
}

二刷，与石子合并的不同点在：

1. 合并项链为1~n+1,len最大值为n+1(从一个数开始，到这个数结束)
2. 分界点k从i+1开始，且f[i][k]+f[k][j]+w[i]w[k]w[j] 而不是f[k+1][j]
3. 最后枚举最大值时，区间为f[i][i+n] 而不是f[i][i+n-1]

#include <iostream>
#include <cstring>

using namespace std;

const int N=210;
int f[N][N],w[2*N];

int main()
{
    int  n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i+n]=w[i];
    }

    for(int len=3;len<=n+1;len++)
    {
        for(int i=1;i<=2*n-len+1;i++)
        {
            int j=i+len-1;
            for(int k=i+1;k<j;k++)
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]+w[i]*w[k]*w[j]);
            }
        }
    }
    int res=0;
    //枚举起点
    for(int i=1;i<=n;i++)
    {
        res=max(res,f[i][n+i]);
    }
    cout<<res;



    return 0;
}