区间DP (2)

问题链接: 能量项链

思路: 区间DP

环形区间展开为链式区间, 定义f[i][j]表示区间[i,j]的能量
转移方程为f[i][j]=f[i][k]+f[k][j]+a[i]*a[k]*a[j]

算法设计

python

from typing import List
class Solution:
    def main(self, n:int, a:List[int]):
        N=2*n
        a.extend(a)
        f=[[0 for _ in range(N)] for _ in range(N)]
        # 区间DP
        for L in range(1, n+2):
            l=0
            while l+L-1<2*n:
                r=l+L-1
                for k in range(l+1, r):
                    f[l][r]=max(f[l][r], f[l][k]+f[k][r]+a[l]*a[k]*a[r])
                l+=1
        res=0
        for i in range(n): res=max(res, f[i][n+i])
        print(res)


if __name__ == '__main__':
    n=int(input())
    a=list(map(int, input().split()))
    a=a[:n] # 需要检测实际读进去的数据数量【测试点9比较特殊】
    sol=Solution()
    sol.main(n, a)

c++

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=205;
int n;
int w[N];
LL f[N][N];

int main(){
    memset(f, 0x00, sizeof f);
    cin>>n;
    for(int i=1; i<=n; ++i){cin>>w[i]; w[i+n]=w[i];}
    for(int len=1; len<=n+1; ++len){ // 枚举区间长度
        for(int l=1; l+len-1<=n*2; ++l){ // 枚举左端点
            int r=l+len-1;
            for(int k=l+1; k<r; ++k){ // 枚举断开点
                f[l][r]=max(f[l][r], f[l][k]+f[k][r]+w[l]*w[k]*w[r]);
            }
        }
    }
    LL res=0;
    for(int i=1; i<=n; ++i) res=max(res, f[i][i+n]);
    cout<<res<<endl;
    return 0;
}