python

6.4 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`AcWing` `320` 能量项链

一、题目描述

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 N 颗能量珠。

能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。

并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 m×r×n（Mars 单位），新产生的珠子的头标记为 m，尾标记为 n。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 N=4，4 颗珠子的头标记与尾标记依次为 (2，3)(3，5)(5，10)(10，2)。

我们用记号 ⊕ 表示两颗珠子的聚合操作，(j⊕k) 表示第 j，k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为：(4⊕1)=10×2×3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。

输入格式 输入的第一行是一个正整数 N，表示项链上珠子的个数。

第二行是 N 个用空格隔开的正整数，所有的数均不超过 1000，第 i 个数为第 i 颗珠子的头标记，当 i<N 时，第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记，第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式 输出只有一行，是一个正整数 E，为一个最优聚合顺序所释放的总能量。

数据范围 4≤N≤100,1≤E≤2.1×10^9

输入样例：

4
2 3 5 10

输出样例：

二、数据样例解析

第二行是N个用空格隔开的正整数，所有的数均不超过 1000，第 i 个数为第 i 颗珠子的头标记，当 i<N 时，第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记，第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

上面这段话，就是告诉我们，其实 是一个首尾相连接的环。

样例： 2 3 5 10 表示有4个珠子：①[2,3], ②[3,5],③[5,10],④[10,2]

如果我们先合并的④和①,最终结果就是⑤[10,3]，释放能量10*2*3=60点，剩下②③⑤ ⑤再与②合并，结果就是⑥[10,5]，释放能量10*3*5=150点。剩下③和⑥ ⑥与③合并，结果就是⑦[10,10]，释放能量10*5*10=500点。剩下⑦,只剩下一个了，完成！

一共合并3次，总的能量就是60+150+500=710点

三、理解题意

本题是上一题环形石子合并问题的变形。按照上一题一样的处理环形问题的方法，将序列的长度翻倍。

状态表示

f[l][r]表示第l到第r个珠子合并释放的最大能量

这里注意比如len为2时，


\large \left\{\begin{matrix}
[2 ~3]  & 前面一个珠子 \\ 
[3 ~5] &  后面一个珠子
\end{matrix}\right.

合并这两颗珠子，释放的能量等于2 * 3 *5。

最后剩下一棵珠子的头尾吸盘也需要合并到一起的，比如2 3 5 10合并成为了(2,10)，尽管此时合并成了一串，但项链的首尾仍需要连接，所以还需要合并(2,10)及(10,2)，本题就转化成了求区间长度为n的石子合并问题的最大值。

四、区间`DP`

#include <bits/stdc++.h>

using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f;

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

int main() {
    scanf("%d", &n);
    // 破环成链
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i + n] = a[i]; // 第 i 颗珠子的头标记

    // 区间DP模板
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n * 2; l++) { // 区间左端点
            int r = l + len - 1;                     // 区间右端点，r-l=l+len-1-l=len-1,举栗子：比如r=3,l=1,则len=3,len-1=3-1=2,符合事实
            for (int k = l; k < r; k++)              // 中间点k
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + a[l] * a[k + 1] * a[r + 1]);
            // 这里的过程同石子合并，这里不难想到若将l到k的珠子合并之后会变成一个首是l而尾k+1的珠子；
            // 同理若将k+1到r的珠子合并之后会变成一个首是k+1而尾r+1的珠子；
        }
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(f[i][i + n - 1], res); // 区间长度为n
    printf("%d\n", res);
    return 0;
}

五、记忆化搜索代码

#include <bits/stdc++.h>

using namespace std;
const int N = 210;

int n;
int a[N];
int f[N][N]; // 记忆化结果

// 计算l~r之间的结果值
int dfs(int l, int r) {
    if (r == l) return 0;                            // 区间内有一个数字
    if (r == l + 1) return (a[l] * a[r] * a[r + 1]); // 区间内有两个数字,a[r+1]就是破环成链的妙用

    int &v = f[l][r]; // 准备记录结果
    if (v) return v;  // 如果计算过，则返回已经有的结果

    // 枚举倒数第一个可能的结束位置
    for (int k = l; k < r; k++)
        v = max(v, dfs(l, k) + dfs(k + 1, r) + a[l] * a[k + 1] * a[r + 1]);
    return v;
}

int main() {
    scanf("%d", &n);
    // 破环成链
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i + n] = a[i];

    // 以每个位置为起点，跑一遍dfs,找出最大值
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, dfs(i, i + n - 1));
    printf("%d", res);
    return 0;
}

6.4 KiB Raw Permalink Blame History Unescape Escape

AcWing 320 能量项链