P1063 能量项链
斯德哥尔摩
2018-10-14 10:08:00
[P1063 能量项链](https://www.luogu.org/problemnew/show/P1063)
头一次写区间$DP$的板子题。。。
其实就是枚举起止点，然后枚举断点，拆分成两个区间，合并成一个大区间。
设$dp[i][j]$表示合并区间$[i,j]$能获得的最大能量。
于是要么不操作（当然不存在的。。。），要么拆成两个区间。
那么转移方程长这个样：
$$dp[i][j]=\max\{dp[i][k]+dp[k+1][j]+v_i\times v_{k+1}\times v_{j+1}|k\in [i,j)\}$$
然后对于首尾相连的情况，直接断环成链，倍长即可。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 210
using namespace std;
int n,ans=-1;
int val[MAXN],dp[MAXN][MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
for(int i=2;i<(n<<1);i++)
for(int j=i-1;i-j<n&&j>=1;j--){
for(int k=j;k<i;k++)dp[j][i]=max(dp[j][i],dp[j][k]+dp[k+1][i]+val[j]*val[k+1]*val[i+1]);
ans=max(ans,dp[j][i]);
}
printf("%d\n",ans);
}
void init(){
n=read();
for(int i=1;i<=n;i++)val[i]=val[i+n]=read();
}
int main(){
init();
work();
return 0;
}
```