个人技术分享

算法提高之能量项链

• 核心思想：区间dp

  • 通过观察发现可以将n个珠子最后的n+1个数看作石子 合并石子

  • 

  • 在l~r的范围内 找k作隔断

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 110,M = N<<1;
    int f[M][M];
    int w[M];
    int n;
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>w[i],w[i+n] = w[i];  //成链
        
        memset(f,-0x3f,sizeof f);  //求最大初始化最小
        for(int len = 2;len <= n+1;len++)  //区间长度
        { 
            for(int l=1,r;r = l+len-1,r<=n<<1;l++)  //遍历左端点
            {
                if(len == 2) f[l][r] = 0;  //说明只有一个珠子
                else
                {
                    for(int k=l+1;k<r;k++)  //k != l不能相同
                    {
                        f[l][r] = max(f[l][r],f[l][k] + f[k][r] + w[l]*w[r]*w[k]);
                    }
                }
            }
        }
        int res=0;
        for(int l=1;l<=n;l++)
            res = max(res,f[l][l+n]);  //每个点都可能是起点
        cout<<res<<endl;
    }