【P1063】 能量项链

之前一直在luogu博客上

2018年12月25日17:15:52     copy到博客园

---

P1063 能量项链

简单的区间dp

通过解决小区间来影响大区间

环形问题 存储的时候存两边 变成 2*N 个元素

code:

for(int i=1;i<=n;i++)
{
    cin>>e[i];
    e[i+n]=e[i];
}

s[i][j] ------- i到j的最大能量

k ------------ 左右区间划分点

把区间分为2个珠子、3个珠子、4个珠子……

s[i][j]=max(s[i][j],左区间能量+右区间能量+合并后的能量)

合并后=左区间第一个珠子右区间第一个珠子总区间最后一个珠子

s[i][j]=max(s[i][j],s[j][k]+s[k+1][i]+e[j]e[k+!]e[j])

Code：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int e[210];
int s[210][210];
int maxn;
int main()
{
    cin.sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i];
        e[i+n]=e[i];
    }
    for(int i=2;i<2*n;i++)
    {
        for(int j=i-1;i-j<n&&j>=1;j--)
        {
            for(int k=j;k<i;k++)
            {
                s[j][i]=max(s[j][i],s[j][k]+s[k+1][i]+e[j]*e[k+1]*e[i+1]);
                maxn=max(maxn,s[j][i]);
            }
        }
    }
    cout<<maxn;
}