[题解]洛谷P1063：能量项链

原题链接：P1063 能量项链

这道题我在数月前曾经试图做过，但是没有什么结果（10分）。现在回顾一下，就先从这个错误的搞法说起。
最开始是前置知识~当然这部分肯定是正确的~

• 本题是环，又要进行dp，所以取模显然有点不合适，这时我们拆环为链！
• 怎么做呢？可以将整个串储存两遍，这样，在锁住“截取长度不超过原本环的长度”之后，就能够轻松dp（雾）而不忽略环的特性导致少考虑情况啦~
• 当然，对应地，既然储存了两遍，在更新时就一定要一并更新╮(╯▽╰)╭

所以本题读入这样写：

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

于是我们稍加思考，大区间的结果由小区间合并而来，合并考虑左边和右边两种情况，取max，即得到状态转移方程：
f[i][j]=max(f[i+1][j]+a[i]*a[i+1]*a[j],f[i][j-1]+a[i]*a[j-1]*a[j]);
OOOOOOOOOOOOOOOOOOOOf course当然是假的。

如果按照我的叙述方法，就很容易发现问题：f[i][j]仅由两种小情况转移而来：

1. 最左侧珠子与右侧合并后“大珠子”合并；
2. 最右侧珠子与左侧合并后“大珠子”合并。

这显然是不完善的。举例：有四个珠子表示为$A$ $B$ $C$ $D$；
$(A+B)$与$(C+D)$合并显然也是一种可行方案，但在上面的状态转移方程中没有任何一种可以表示该情况。

搞清错哪了就能轻松收掉了。

重写状态转移方程，在区间[i,j]中同时枚举分割点即可。
f[i][j]=max(f[i][j],f[i][k]+a[i]*a[k]*a[j]+f[k][j]);

即可AC -> R16208474

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 207;
typedef long long ll;
int a[MAXN];
ll f[MAXN][MAXN];
int main(){
    int N;
    scanf("%d",&N);
    memset(a,0,sizeof(a));
    memset(f,0,sizeof(f));
    for(int i=1;i<=N;i++)scanf("%d",&a[i]),a[i+N]=a[i];
    ll ans=0;
    for(int j=3;j<=(N<<1);j++){
        for(int i=j-2;i>0&&j-i<=N;i--){
            for(int k=i+1;k<j;k++){
                f[i][j]=max(f[i][j],f[i][k]+a[i]*a[k]*a[j]+f[k][j]);
            }
            if(j-i==N)ans=max(ans,f[i][j]);
        }
    }
    printf("%lld",ans);
    return 0;
}

版权声明：本文是原创文章，版权归 无限UCW 所有。

本文链接：https://ucw.moe/archives/solution-luogu-p1063.html

本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。