解题报告 P1063 能量项链【NOIP2006TGT1】

题目内容

P1063

本题对于题意的理解很重要

Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是 Mars 人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m,尾标记为 r,后一颗能量珠的头标记为 r,尾标记为 n,则聚合后释放的能量为 m \times r \times nMars 单位),新产生的珠子的头标记为 m,尾标记为 n

需要时,Mars 人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。

例如:设 N=44 颗珠子的头标记与尾标记依次为 (2,3) (3,5) (5,10) (10,2)。我们用记号 表示两颗珠子的聚合操作,(j⊕k) 表示第 j,k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为:

(4⊕1)=10 \times 2 \times 3=60=10×2×3=60

第一行是一个正整数 N(4≤N≤100),表示项链上珠子的个数。第二行是 N 个用空格隔开的正整数,所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记 (1≤i≤N),当 i 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。

解题思路

一个项链,说明是环形区间 dp,但这题比较注重细节。我们设 f(i,j) 表示区间 [i,j] 上的所有珍珠合并后能释放的最大能量,而 a_i 又是第 i 颗珠子的头标记,所以我们有如下的状态转移方程:

f(i,j)=\max_{k\in [i,j)}\lbrace f(i,k)+f(k+1,j)+a_i\times a_{k+1}\times a_{j+1}\rbrace

这个方程的解释:首先枚举 k 作为断点,表示将区间 [i,k](k,j] 的珠子合并,而合并释放的能量是前珠子的头标记乘 k 珠子的尾标记乘后珠子的尾标记,必须清楚自己设的东西表示的是什么否则就是像我一样调半个小时

除此之外没有什么难点,代码见下:

#include <cstdio>
inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=205;
int n,f[maxn][maxn],a[maxn];

//f[i][j]表示[i,j]区间内的珠合并后能达到的最大价值

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        a[n+i]=a[i];//常规环状展开
    }
    int ans=0;
    for(int l=2;l<=n;l++)//l表示枚举的区间长度
        for(int i=1,j=i+l-1;i<n<<1&&j<=n<<1;i++,j++)//枚举左右端点
            for(int k=i;k<j;k++)//然后枚举中间断点
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);//转移方程
                ans=max(ans,f[i][j]);//其实可以直接统计答案
            }
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注