P1063 [NOIP2006 提高组] 能量项链

就非要用项链吗

思路

有点像 #P1775. 石子合并（弱化版） 和 #P1880. [NOI1995] 石子合并

由于 nPr123f 是 **，DP 总是爆炸，所以我们用 大力飞砖 记忆化搜索 解决

这一次，我不用复制数组的方法破环，而是直接定义两个函数，计算出“上一个”和“下一个”珠子的位置。

int Next(int x)
{
    return x == n ? 1 : x + 1;  // 到底就回到开头
}

int Prev(int x)
{
    return x == 1 ? n : x - 1;  // 同理
}

接下来，开始编写搜索。

设 $f(l, r)$ 为将 $[l, r]$ 处的珠子合并可以释放的最大能量值

怎么算这个 $f(l, r)$ 呢？

沿用 #P1775. 石子合并（弱化版） 的思路：

枚举中间端点 $i$，递归计算 $f(l, i) + f(Next(i), r)$，再加上两颗大珠子的能量，每次循环取最大值。

主程序中，每个起点都试一遍即可。

代码

#include <cstdio>
#include <algorithm>
#define N 105

using namespace std;

int a[N] = {}, f[N][N] = {}, n, ans;

int Next(int x)
{
    return x == n ? 1 : x + 1;  // 到底就回到开头
}

int Prev(int x)
{
    return x == 1 ? n : x - 1;  // 同理
}

int dfs(int l, int r)
{
    int& ans = f[l][r];         // 声名一个引用，对 ans 的读写都对 f[l][r] 进行
    if (ans) return ans;        // 算过就不算了

    for (int i = l; i != r; i = Next(i))
        ans = max(ans, dfs(l, i) + dfs(Next(i), r) + a[l] * a[Next(i)] * a[Next(r)]);   // 递归计算，加上两颗大珠子的能量
    
    return ans;
}

int main()
{
    scanf("%d", &n);    // 输入

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    ans = -1;

    for (int i = 1; i <= n; i++)    // 每个起点都尝试一遍
        ans = max(ans, dfs(i, Prev(i)));    // 取最大值

    printf("%d", ans);  // 输出

    return 0;
}

制作不易，请点个赞！