NOIP 2006提高组 能量项链

经典环形dp问题

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int lenght=0,DG[2005][2005]={0};
int li[2005][2]={0};
int DP(int lf,int rt);

int main(void)
{
 cin>>lenght;
 for(int i=1;i<=lenght;i++)
    {
     cin>>li[i][0]; 
     if(i!=1)li[i-1][1]=li[i][0];
    }
 li[lenght][1]=li[1][0];
 for(int i=lenght+1;i<=lenght*2-1;i++)
    {
     li[i][0]=li[i-lenght][0];
     li[i][1]=li[i-lenght][1];
    }
 int ans=0,t=0;
 for(int i=1;i<=lenght;i++)
    {
     t=DP(i,i+lenght-1);
     ans=max(t,ans);
    }
 cout<<ans<<endl;
 return 0;
}

int DP(int lf,int rt)
{
 if(DG[lf][rt]!=0)return DG[lf][rt];
 if(rt==lf+1)return li[rt][0]*li[rt][1]*li[lf][0];
 int tot=0,as=0;
 for(int i=lf;i<rt;i++)
    {
     tot=DP(lf,i)+DP(i+1,rt)+(li[lf][0]*li[i+1][0]*li[rt][1]);
     as=max(tot,as);
    }
 DG[lf][rt]=as;
 return as;
}