menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】DP——能量项链
2020-05-16 | 【OI】 | 暂无评论 | 65 次阅读 | 330字

    好,我们接着下一题。题目链接放在这了:
https://www.luogu.com.cn/problem/P1063
    这是一道关于环的题目,所以说首先我们就要把它拆成一条链。就好比说本来这个环长这样:

      1
     2 3
    4   5
   6     7
  8       9
 5         0
  4       5
   7     6
    5   8
     9 0
      6
      

    然后我们就要把它变成这样子:

1 3 5 7 9 0 5 6 8 0 6 9 5 7 4 5 8 6 4 2

    但是,由于我们并没有确定这个环的开头和结尾,所以我们需要让这条链展现出这个环的所有形态,也就是展现出所有的开头结尾。怎么办呢?很简单,把整条链复制一遍拼接在结尾就好了,就像这样:

1 3 5 7 9 0 5 6 8 0 6 9 5 7 4 5 8 6 4 2 1 3 5 7 9 0 5 6 8 0 6 9 5 7 4 5 8 6 4 2

    然后,因为开头和结尾不能是同一个数字,所以说这条拼接完成之后的长链的最后一个可以去掉,变成这样:

1 3 5 7 9 0 5 6 8 0 6 9 5 7 4 5 8 6 4 2 1 3 5 7 9 0 5 6 8 0 6 9 5 7 4 5 8 6 4

    好,接下来我们就可以来推转移方程了。

//我们把f[i][j]设置成在i->j的区间内能量的最高值,然后就可以得出以下方程
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+num[i]*num[k+1]*num[j+1]);

    DP过完之后,输出答案这里要注意一下。由于我们把一个环拆成了一条链,而且有多个开头结尾,所以我们要在这条链中枚举每一个开头结尾,来获得最大值,像这样:

for(int i=1;i<=2*n;i++)
        if(f[i][i+n-1]>maxn)
            maxn=f[i][i+n-1];

    所以,最后完整代码就是这样:

#include <bits/stdc++.h>
#define MAXN 450
using namespace std;
int num[MAXN];
int f[MAXN][MAXN];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        num[i+n]=num[i];
    }
    for(int i=2*n;i>=1;i--)
        for(int j=i+1;j<=2*n;j++)
            for(int k=i;k<j;k++)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+num[i]*num[k+1]*num[j+1]);
    int maxn=0;
    for(int i=1;i<=2*n;i++)
        if(f[i][i+n-1]>maxn)
            maxn=f[i][i+n-1];
    cout<<maxn<<endl;
    return 0;
}


真香(^-^)V
    好,本题记录到这里,我们下一题见。

None
发表评论
暂无评论
textsms
account_circle
email
link
arrow_back 上一篇
arrow_forward 下一篇