洛谷 P1063 [NOIP 2006 提高组] 能量项链

// P1063 [NOIP 2006 提高组] 能量项链 —— ★ 这一版就能 AC。
//
// ★★ 关键的一步（一）：**区间的端点是「标记」，不是「珠子」。**
//   第 i 颗珠子是 (aᵢ, aᵢ₊₁) —— 它由**两个相邻的标记**夹出来。
//   所以一段连续的珠子 = 一段连续的标记，而「合并」正好把中间那个标记吃掉：
//
//       f[l][r] = max over k in (l, r) of ( f[l][k] + f[k][r] + a[l] × a[k] × a[r] )
//
//   ⚠ 注意断点那两项是 `f[l][k]` 和 `f[k][r]` —— **k 同时是左半的右端和右半的左端**，
//     不是 `f[k+1][r]`。写成 `k+1` 就等于把「标记」当成「珠子」在切（见 p1063K1.cpp）。
//
// ★★ 关键的一步（二）：**破环成链** —— 和 [P1880](/sol/p1880/) 一样，
//   把标记复制一遍（2N 个），跑长度为 N 的区间，答案取每个起点的最大值。
//
// ⚠ 题面那句「`E ≤ 2.1 × 10⁹`」正好卡在 `int` 上限 2 147 483 647 的**里面一点点**
//   （余量只有 2.3%）—— 它是**出题人替你挡掉的**，不是能从数据范围推出来的
//   （推出来的上界是 `99 × 1000³ ≈ 9.9 × 10¹⁰`）。这里照旧用 `long long`，
//   那样就不依赖那份信任。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    int m = 2 * n;
    vector<long long> a(m + 2, 0);
    for (int i = 1; i <= n; i++) {
        if (scanf("%lld", &a[i]) != 1) return 0;
        a[i + n] = a[i];                                  // 破环成链
    }
    a[m + 1] = a[1];                                      // 链上最后一个标记

    // f[l][r]：把标记 l..r 之间那些珠子全合成一颗，最多能释放多少能量
    vector<vector<long long>> f(m + 2, vector<long long>(m + 2, 0));
    for (int len = 2; len <= n; len++)                    // len = 这一段有几颗珠子
        for (int l = 1; l + len <= m + 1; l++) {
            int r = l + len;                              // 标记下标：l..r 共 len 颗珠子
            long long best = 0;
            for (int k = l + 1; k < r; k++)               // ★ k 是被吃掉的那个标记
                best = max(best, f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
            f[l][r] = best;
        }

    long long ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, f[i][i + n]);
    printf("%lld\n", ans);
    return 0;
}

// ✗ P1063 的第一个坑：**没破环**（当成一条直的项链做）。
//
// 题面写得很清楚「项链」是一个环：第 N 颗珠子的尾标记等于第 1 颗的头标记。
// 这一版只跑 f[1][n+1]，等于规定「必须最后合并第 N 颗和第 1 颗之间那一处」。
//
// ★ 方向能先说死：它只是把可行方案砍掉了一部分 ⇒ **答案恒 ≤ 正解**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    vector<long long> a(n + 2, 0);
    for (int i = 1; i <= n; i++) if (scanf("%lld", &a[i]) != 1) return 0;
    a[n + 1] = a[1];

    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len <= n + 1; l++) {
            int r = l + len;
            long long best = 0;
            for (int k = l + 1; k < r; k++)
                best = max(best, f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
            f[l][r] = best;
        }
    printf("%lld\n", f[1][n + 1]);
    return 0;
}

// ✗ P1063 最典型的那个坑：断点写成了 `f[k+1][r]`。
//
// 石子合并里写的是 `f[l][k] + f[k+1][r]` —— 因为那里的区间装的是**堆**，
// 一个堆要么属于左边要么属于右边，不能两边都算。
//
// ⚠ 而这道题的区间端点是**标记**：`k` 这个标记**同时是左半的右端和右半的左端**
//   （它正是那次合并被吃掉的那个标记）。所以必须写 `f[l][k] + f[k][r]`。
//   照着上一题的手感写成 `k+1`，就等于把标记当成了珠子在切。
//
// ★ 页面上量过：它**恒 ≤ 正解**（300/300），而且 `n` 一大就几乎必被抓
//   （n ≤ 20 时 295/300，n ≤ 100 时 **300/300**）。
// ⚠⚠ 可**官方样例偏偏放过了它**（照样打出 710）—— 因为样例的 `n = 4`
//   正好是题面允许的最小值，切错一格几乎没差别。
//   ⇒ 又一次「样例挡不挡得住，只能一个一个试」。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    int m = 2 * n;
    vector<long long> a(m + 2, 0);
    for (int i = 1; i <= n; i++) { if (scanf("%lld", &a[i]) != 1) return 0; a[i + n] = a[i]; }
    a[m + 1] = a[1];

    vector<vector<long long>> f(m + 2, vector<long long>(m + 2, 0));
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len <= m + 1; l++) {
            int r = l + len;
            long long best = 0;
            for (int k = l + 1; k < r; k++)
                best = max(best, f[l][k] + f[k + 1][r] + a[l] * a[k] * a[r]);   // ✗ k+1
            f[l][r] = best;
        }
    long long ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, f[i][i + n]);
    printf("%lld\n", ans);
    return 0;
}