题目描述

blablabla

样例

blablabla

算法1（区间dp）

(状态计算)

f[l][r] = max(f[l][r],f[l][k] + f[k][r] + a[l]a[r]a[k]);

时间复杂度

参考文献

《算法提高课》

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 210;

int f[N][N];
int a[N];

int n;

int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n; i ++ )
    {
        cin >> a[i] ;
        a[i+n] = a[i];
    }
    for(int len = 3 ; len <=  n+ 1 ; len ++ )
    for(int l = 1; l + len - 1 <= 2 * n ; l ++ )
    {
        int r = len + l - 1 ;
        for(int k = l + 1 ; k < r; k ++ )
        {
            f[l][r] = max(f[l][r],f[l][k] + f[k][r] + a[l]*a[r]*a[k]);
        }
    }

    int res = 0;

    for(int i = 1 ; i <=n ; i ++  ) res = max( res ,f[i][i+n]);


    cout << res << endl;

    return 0 ;
}