P1063能量项链

这又是一道经典的区间DP题。

复习一下区间DP的做法。

三重循环，第一层枚举区间长度，第二层枚举起点，第三层枚举断点。

区间长度是从1到n-1(因为如果是从1到n的话，1+n≠n，所以是1到n-1)。注意这里的n就是总的元素个数（一般就是题目中给出的n,而不是处理完环变链之后的总数（2*n-1））

但是在枚举起点的时候要特别注意，要使这次枚举起点的最大值+当前枚举的区间长度=链的最后一个元素的编号。

举个栗例子：在这道题里，我们这样枚举：

for(int len=;len<=n;len++)//一开始我设的是end=st+len-1,不过等价于上面所说的len从1到n-1,end=st+len

        for(int st=;st<=2*n-len+1;st++)//注意枚举的终止条件

感性理解一下ρωρ

枚举断点的时候，断点k是从st枚举到end-1(如果枚举到end,则k+1=end+1,f[end+1][end]没有实际意义)

通用的做法讲完了,来扯一下这道题

用h[i]，表示i号点的头标记(head),用t[i]表示i节点的尾标记（tail）,f[i][j]表示从第i个点合并到第j个点的最大得分，初始化：f[i][i]=0(因为你不需要合并，当然也没有得分)

从读入开始，就是坑。因为我们要在读入头标记的时候计算尾标记,h[i]=t[i-1]。我们注意到，点的编号从1开始，1-1是0，但是不存在0号点，所以要特判掉。并且这里还牵扯到环变链，所以也要计算h[i+n],t[i+n]。

读入完了，我们发现接下来就是一个标准的区间DP板子，只需要注意上面所提到的枚举的起止点就可以了。

递推式：f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+h[i]*t[k]*t[j])

最后答案注意不是f[1][n]，而是在f[i][i+n-1]（1<=i<=n）中选择最大值（不一定要从1节点开始合并）

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,h[N*],t[N*],f[N*][N*];

int read()//快读

{

    char ch=getchar();

    int x=;bool f=;

    while(ch<''||ch>'')

    {

        if(ch=='-')f=;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    f?x=-x:x=x;

    return x;

}

int main()

{

    n=read();

    for(int i=;i<=n;i++)

    {

        h[i]=read();

        int r=i-;if(r==)r=n;//pay attention

        t[r]=h[i];

        h[i+n]=h[i];

        t[r+n]=t[r];

    }

    for(int len=;len<=n;len++)//len=r-l+1

    {

        for(int st=;st<=*n-len+;st++)//注意一下

        {

            int end=st+len-;

            for(int k=st;k<end;k++)

            {

                f[st][end]=max(f[st][end],f[st][k]+f[k+][end]+h[st]*t[k]*t[end]);

            }

        }

    }

    int maxn=-;

    for(int i=;i<=n;i++)

     maxn=max(maxn,f[i][i+n-]);//找答案

    printf("%d",maxn);

}

巴特西

P1063能量项链

最新文章

热门文章