算法提高课汇总

算法思路

理解题意

思路与AcWing 1068. 环形石子合并类似, 在实现细节上略有不同.

实现细节

• 用相邻的两个值表示一个能量石(也可看为矩阵), 所以枚举$N$个石头需要的长度是$N + 1$.

  在环形石子合并中, 因为长度为$N$, 所以实际上$2N$的链中$N + 1\sim 2N$
  与$1\sim N$区间重复冗余了. 而本题长度$N + 1$, 没有冗余的情况.

• 除长度$2N$链的首尾两端, 每个值都是被两个能量石复用的, 所以状态计算时$dp(i, k) + dp(k, j)$, $k$
  是左右两端的能力石的共有属性值的下标.

• 每个石头需要两个值表示, 所以$i\lt k\lt j$.

• 子集的划分方式(即$k$的取值)不同最后一次合并的收益不同, 而环形石子合并问题中划分方式
  不同对最后一次合并无影响.

实现代码

#include <iostream>

using namespace std;

const int N = 210;

int n;
int w[N];
int dp[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 <= 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] + w[i] * w[k] * w[j] );
            }
        }
    }

    int res = 0;
    for( int i = 1; i <= n; i ++ )  res = max( res, dp[i][i + n] );
    cout << res << endl;

    return 0;
}