P1063

题目传送门

使用的是区间DP

50分 WA #1、#4、#8、#9、#10

代码见下

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    ll l,r;//头尾标记
};
node a[1000];//珠子数组
ll dp[1000][1000],n;
node fun[1000][1000];//fun数组记录合并完后的头尾标记

int main(int argc, char const *argv[])
{
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        scanf("%lld", &a[i].l);
        if(i>1) a[i-1].r=a[i].l;
    }
    a[n].r=a[1].l;
    for(int i=n+1; i<2*n/*加不加等于都试过了*/; ++i) a[i]=a[i-n];//断环成链
    for(int i=1; i<2*n/*和上面一样*/; ++i)
    {
        dp[i][i]=0;
        fun[i][i].l=a[i].l, fun[i][i].r=a[i].r;
        //初始化长度为一的情况
    }
    for(int len=2; len<=n; ++len)
    {
        for(int i=1;i<=n; ++i){

            int j=i+len-1;
            if(j>=2*n) break;//处理越界
            //cout<<i<<' '<<j<<endl;
            for(int k=i; k<j; ++k)
            {
                if(dp[i][j]<fun[i][k].r*fun[i][k].l*fun[k+1][j].r+dp[i][k]+dp[k+1][j])//发现更优状态
                {
                    //printf("Find %d, %d, %d better. ",i,k,j);
                    //printf("dp[%d][%d]=%d\n",i,j,fun[i][k].r*fun[i][k].l*fun[k+1][j].r);
                    dp[i][j]=fun[i][k].r*fun[i][k].l*fun[k+1][j].r+dp[i][k]+dp[k+1][j];//状态转移
                    fun[i][j].l=fun[i][k].l,fun[i][j].r=fun[k+1][j].r;//更新选择
                }
            }
        }
    }
    long long ans=0;
    for(int i=1; i<=n; ++i)
    {
        ans=max(ans, dp[i][n+i-1]);//打擂台找最优解
    }
    cout<<ans;
    return 0;
}