洛谷 P1063 能量项链

然而在提高组的动归里居然还有这样一道水题。

把环拆成链，然后愉快的区间动归。

枚举起始位置，枚举区间长度，枚举断开位置，

然后找最大的方案记录下来。

思路明了，十分简单。

#include<iostream>
using namespace std;

int len,head[1001],tail[1001],f[1001][1001],n;

void read()
{
 int i,j,k,max1;
 
 cin>>n;
 cin>>head[1];
 for(i=2; i<=n; i++)
 {
  cin>>head[i]; 
  tail[i-1]=head[i];
 }
 tail[n]=head[1];
 for(i=n+1; i<=2*n-1; i++)
 {
  head[i]=head[i-n];
  tail[i]=tail[i-n];
 }
 
 //核心代码 
 for(len=1; len<=n; len++)//区间长度
   for(i=1; i<=2*n-len-1; i++)
   {
      j=i+len;
    for(k=i; k<=j-1; k++)//寻找断开点 
      f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);//动态转移方程 
   } 
 
 max1=0;
 for(i=1; i<=n; i++)
   if(f[i][i+n-1]>max1)
     max1=f[i][i+n-1];//找最佳开始点 
 cout<<max1<<endl;
    return;
}

int main()
{
 read();
 return 0;
}

AC代码。