[题解]洛谷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;
}
最后修改:2019 年 02 月 21 日 06 : 24 PM
欢迎投食喵 ~

发表评论

1 条评论

  1. 魄筱

    完全看不懂(╯‵□′)╯︵┴─┴