能量项链(环,动归)

http://codevs.cn/problem/1154/

在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为mrn,新产生的珠子的头标记为m,尾标记为n。

通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请计算一串项链能释放出的最大能量。


从i到j的最大能量:

f(i,j)=max{f(i,k)+f(k+1,j)+x[i]x[k+1]x[j+1]},i<=k<=j-1

注意处理环中i>j的情况,以及j+1越界的情况


#include <iostream>
using namespace std;

int x[100],n,cache[100][100];

int max(int i, int j)
{
    if(cache[i][j]!=-1)
        return cache[i][j];

    int big=0, now;
    if(i<j)
    {
        for(int k=i; k<j; k++)
        {
            now= x[i]*x[k+1]*x[(j+1)%n] +max(i,k) +max(k+1,j);
            if(now>big)
                big=now;
        }
    }
    else
    {
        for(int k=i; k<n-1; k++)
        {
            now= x[i]*x[k+1]*x[j+1] +max(i,k) +max(k+1,j);
            if(now>big)
                big=now;
        }
        now= max(i,n-1) +max(0,j) +x[i]*x[0]*x[j+1];
        if(now>big)
            big=now;
        for(int k=0; k<j; k++)
        {
            now= x[i]*x[k+1]*x[j+1] +max(i,k) +max(k+1,j);
            if(now>big)
                big=now;
        }
    }

    cache[i][j]=big;
    return big;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>x[i];

    for(int i=0,j ;i<n;i++)
        for(j=0;j<n;j++)
        {
            if(i==j)
                cache[i][j]=0;
            else
                cache[i][j]=-1;
        }
    cache[n-1][0]=x[n-1]*x[0]*x[1];

    int big=max(0,n-1),now;
    for(int i=1;i<n;i++)
    {
        now=max(i,i-1);
        if(big<now)
            big=now;
    }

    cout<<big;

    return 0;
}

发布者

胡中元

《中原驿站》站长

发表评论

您的电子邮箱地址不会被公开。