以区间DP为前提的【洛谷p1063】能量项链

时间：2022-12-31 15:16:10

（跑去练习区间DP，然后从上午拖到下午qwq）

能量项链【题目链接】

然后这道题也是典型的区间DP。因为是项链，所以显然是一个环，然后我们可以仿照石子合并一样，把一个有n个节点的环延长成为有2*n个节点的链。然后注意最后一个节点2*n的尾标记=第一个节点的头标记；

然后按照区间DP的常规操作：枚举区间长度，这里我枚举的是将几个能量珠聚合在了一起；

然后枚举左端点：同时保证右端点不会超出2*n的范围；

定义右端点：j=i+num-1；

接下来枚举断点；

枚举断点比较关键，断点枚举要从i~j-1，（咱也不知道为啥咱也想不明白，总之当k=j时会重复计算f[i][j]）

转移方程：f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);

因为这里是先将第1~k堆石子合并为1堆，再将k+1~j堆石子合并为1堆，因此将i~j合并时，现在的两颗珠子：

以区间DP为前提的【洛谷p1063】能量项链，所以+head[i]*tail[k]*tail[j]；

然后最后还是枚举（相当于枚举以哪个点为断点），求最大值；

CODE：

#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int ans=0;
    char last=' ',ch=getchar();
    while(ch>'9'||ch<'0') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

int n;
int head[202],tail[202];
int f[202][202];

int main(){
    n=read();
    for(int i=1;i<=n;i++)
      head[i]=read(),head[i+n]=head[i];
    for(int i=1;i<=2*n-1;i++)
      tail[i]=head[i+1];
    tail[2*n]=head[1];
    
    for(int num=2;num<=n;num++){
        for(int i=1;i+num-1<=2*n;i++){
            int j=i+num-1;
            for(int k=i;k<=j-1;k++)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);
    cout<<ans<<endl;
    return 0;
}

end-

　　

标签：

相关文章