洛谷P1063 能量项链讲解

· · 个人记录

洛谷P1063 能量项链讲解

题意描述

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m \times r \times n（Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设N=4，4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j,k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为： $((4⊕1)⊕2)⊕3)=10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710$。 ## 思路和分析 显而易见，本题是一个经典的区间动态规划。 这一类区间$dp$的基本思路就是先分割再合并。 我们不难考虑一个区间最大能量值的计算方法： 对于2个珠子的区间：仅一种方案，即$e=a[l]\times a[r]\times a[r+1]$. 3个：考虑2种情况：①左区间能量与最后一颗合并； ②右区间能量与第一颗合并。（合并时，能量为左区间第一颗$\times$右区间第一颗$\times$区间后一颗） ...... 一直推下去，不难得到状态转移方程：$e=max(e,left+right+new)

注意事项

  1. 由于题目中给的是环，所以要开2倍以上数组还原成链。
  2. 合并时边界需要处理好。
  3. 最终结果要赋初值。

代码

其中，a[i]表示珠子，i表示左边界，j表示右边界，k用来分割左右边界，f[j][i]表示能量，res表示最大值（结果）。

请自行忽略register

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,res=0;
int a[210],f[210][210];
inline int maxx(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i+n]=a[i];
    }
    for(register int i=2;i<n+n;i++)
    {
        for(register int j=i-1;j>=1&&i-j<n;j--)
        {
            for(register int k=j;k<i;k++)
                f[j][i]=maxx(f[j][i],f[j][k]+f[k+1][i]+a[j]*a[i+1]*a[k+1]);
            if(f[j][i]>res) res=f[j][i];
        }
    }
    printf("%d",res);
    return 0;
}

谢谢各位dalao的聆听~

Author:802 zyh