首页 > 其他 > 详细

P1063 能量项链

时间:2018-12-15 10:08:47      阅读:208      评论:0      收藏:0      [点我收藏+]

  思路很清晰:对于dp[i][j]代表以第i个为起始,第j个为结束的最优组合方式,每一次对于其中的一个k进行操作即可。

  还有就是对于环状关系的简便存储方式,只是记得改2*n个点而不是n个。

  代码:

#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 200
int a[maxn],dp[maxn][maxn],n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i+n]=a[i];
    }
    for(int i=2;i<=n+1;i++)
    {
        for(int l=1;l+i<=2*n;l++)
        {
            int r=l+i;
            for(int k=l+1;k<r;k++)
            dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    ans=max(ans,dp[i][i+n]);
    printf("%d",ans);
    return 0; 
}

 

P1063 能量项链

原文:https://www.cnblogs.com/popo-black-cat/p/10122365.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!