如何处理环的问题

吾开一一维数组,以DP为算法,解题。然仅得一半之分。思之良久,乃悟应为未虑环之问题。故以之求教。
附代码
c++
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int n=0;//项链上珠子的个数
int e[102]={0}; //珠子上的头标记
int f[102][102]={0}; //代表合并珠子上的第几到第几个的最大能量
freopen("energy.in","r",stdin);
freopen("energy.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&e[i]);
}
e[0]=e[n];
e[n+1]=e[1];
for (int i=0;i<=n;i++)
f[i][i+1]=e[i]*e[i+1]*e[i+2];
for (int p=1;p<=n;p++)
for (int i=0;i<=n;i++)
for (int j=i+1;j<=n+1;j++)
if ((j-1)!=i)
for (int k=i;k<j;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+e[i]*e[k+1]*e[j+1]);
}
for (int k=0;k<=n;k++)
{
f[1][n]=max(f[1][n],f[1][k]+f[k+1][n]+e[1]*e[k+1]*e[n+1]);
}
f[1][n]=max(f[0][n-1],f[1][n+1]);
printf("%d",f[1][n]);
}

3 条评论

  • @ 2017-12-03 09:27:19

    还是想笑...

  • @ 2016-08-31 09:30:43

    不难得知于环中,必有两个最后合并。不如枚举之,即将环以每一点为头展开成链,然即为矩阵连乘。

  • @ 2016-08-29 09:18:50

    ...........................
    ...........................

    ............................
    ...........................
    ...............................

  • 1

信息

ID
1312
难度
4
分类
动态规划 | 环形DP 点击显示
标签
递交数
5918
已通过
2387
通过率
40%
上传者