能量项链

能量项链

有n个能量珠连成的一个环，第i个能量珠有一个属性，用二元组\((a_i,b_i)\)表示，意味珠首的数字为\(a_i\)，珠尾的数字为\(b_i\)，现在每次操作可以选择两个相邻的能量珠\((a_i,b_i),(a_{i+1},b_{i+1})\)，合并之后为能量珠\((a_i,b_{i+1})\)，并释放能量\(a_i\times b_i\times b_{i+1}\)，其中，保证\(b_i=a_{i+1}\)，求释放的最大能量,\(n\leq 100\)。

解

首先合并相邻两个点，区间递推无疑了，先拆环成链，再在原序列补一截一模一样的序列,于是设\(f[i][j]\)表示合并珠子i到j的释放的最大能量，因为珠i的首数和珠j的尾数必然保留到最后的合并，最后只要枚举个k即可，因此有

\[f[i][j]=\max_{k=i}^{j-1}\{f[i][k]+f[k+1][j]+a_i\times a_{k+1}\times b_{j+1}\}\]

边界：\(f[i][i]=0\),其余无限小

答案：\(\max_{i=1}^n\{f[i][i+n-1]\}\)

参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
int a[201],dp[201][201];
il int max(int,int);
int main(){
    int n,n2;scanf("%d",&n);
    memset(dp,-2,sizeof(dp)),n2=n<<1;
    for(int i(1);i<=n;++i)
        scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i(1);i<=n2;++i)dp[i][i]=0;
    for(int i,j(1),k;j<=n2;++j)
        for(i=j-1;i;--i)
            for(k=i;k<j;++k)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]
                             +a[i]*a[j+1]*a[k+1]);
    int ans(0);for(int i(1);i<=n;++i)ans=max(ans,dp[i][i+n-1]);
    printf("%d",ans);
    return 0;
}
il int max(int a,int b){
    return a>b?a:b;
}

能量项链

原文：https://www.cnblogs.com/a1b3c7d9/p/11001539.html