JDOJ-1089: 能量项链

Description

给你一个序列，首尾相连成一个环，每个位置有head[i]，tail[i]的值，并且head[i]==tail[i-1]，每次将两个相邻位置上的值合并，收益为head[i]*tail[i]*tail[i+1]。新形成上的位置的head[new]=head[i]，tail[new]=tail[i+1]，问合并成最后一个时最大的收益。

由于有环的存在，所以一开始想到加倍然后进行区间DP，也就是枚举大区间断开端点形成的两个小区间更新。然而，由于每次要抠出长度为n的序列，O(n⁴)感觉会T，并且还进行了很多重复性的更新。

正解的话，直接在环上区间DP，这样的话，每次取模，也可做。不过就要注意一下循环的继续条件，还有一定记住中间只要编号变动都要取模。O(n³)裸过。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,head[110],tail[110],ans=-1<<30;
int dp[110][110];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&head[i]);
        tail[(i-1+n)%n]=head[i];
    }
    for(int i=1;i<n;i++)
        for(int l=0;l<n;l++)
        {
            int r=(l+i)%n;
            for(int j=l;j!=r;j=(j+1)%n)
                dp[l][r]=max(dp[l][r],dp[l][j]+dp[(j+1)%n][r]+head[l]*tail[j]*tail[r]);
        }
    for(int i=0;i<n;i++)
        ans=max(ans,dp[i][(i+n-1)%n]);
    printf("%d",ans);
    return 0; 
}