[区间DP]洛谷P1063 能量项链

题意

样例

样例输入：

4
2 3 5 10

样例输出:

710

思路

1.经典区间DP题 算是合并石子的变种 只不过由一个点变成了一个区间
不过我们也可以用结构体存储 当做一个点来看
dp[l][r]表示区间[l,r]能释放的最大能量和
则dp[l][r]可通过子区间dp[l][k]和dp[k+1][r]合并得到 (l<=k<r)
再加上两个子区间合并释放的能量即可

2.由于是一个环 需要拆环为链
即将n扩展为2*n-1
最后答案在max(dp[i][n+i-1]) (1<=i<=n) 中

总结

经典的区间DP题
需要理解先枚举区间长度 再枚举左端点来确定子区间的思想
注意遇到链时 要拆环为链

代码

#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<queue>
#define MAXN 100010
#define INF 0x7ffffff
#define ll long long
using namespace std;
int n;
struct node
{
    int left,right;
}a[2010];
int b[1000];
int dp[1000][1000];//dp[l][r]表示区间[l,r]能取得的最大能量
int main()
{
    cin>>n;
    int first=0;
    for(int i=1;i<=n;i++)   cin>>b[i];
    for(int i=1;i<n;i++)   a[i].left=b[i],a[i].right=b[i+1];
    a[n].left=b[n];a[n].right=b[1];
    for(int i=1;i<=n;i++)   a[n+i].left=a[i].left,a[n+i].right=a[i].right;

    for(int len=2;len<=n;len++)
        for(int i=1;i<=2*n-1-len+1;i++)
        {
            int l=i,r=i+len-1;
            for(int k=l;k<r;k++)
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l].left*a[k].right*a[r].right);
        }
    int ans=0;
    for(int i=1;i<=n;i++)   ans=max(ans,dp[i][n+i-1]);
    cout<<ans<<endl;
    system("pause");
    return 0;
}