1. 题目

传送门= ̄ω ̄=
(真是又臭又长的题面)
论为何现在我做题老看不清题

2. 题解

很水的一道环形dp题。。。
首先剖环为链:复制一遍元素(老套路了)。。。

设$f(i,j)$为区间$[i,j]$的珠子聚合后产生的最大能量。
$f(i,j)=max\{f(i,k)+f(k+1,j)+e[i]\cdot e[k+1]\cdot e[j+1]|i<=k<j\}$

代码:

#include <bits/stdc++.h>
using namespace std;
int n,arr[205],f[205][205],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]),arr[i+n]=arr[i];
    for(int l=1;l<n;l++)
        for(int i=1;i<=(n<<1)-l;i++)
            for(int j=i;j<i+l;j++)
                f[i][i+l]=max(f[i][i+l],f[i][j]+f[j+1][i+l]+arr[i]*arr[j+1]*arr[i+l+1]);
    for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);
    printf("%d\n",ans);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

boshi · 2017年5月30日 12:49 下午

%%%压行太强了

    konnyakuxzy · 2017年5月30日 7:52 下午

    啊,我的gedit设置tab宽度为2。
    所以我这边看起来还是很正常的

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *