P1063 [NOIP2006 提高组] 能量项链 题解

· · 题解

这道题细节坑点很多，基本思路是区间DP

题目传送门

思路

性质

区间DP的其中一种有一个特点(性质):大区间的解能由小区间的解合并而来。

聚合的本质

而通过读题我们可以得到，一串珠子聚合后，本质还是一个珠子，其头标记是最前面（左端点）的头标记，其尾标记是最后面（右端点）的尾标记，只不过带了聚合的能量而已

那么，我们可以想到，一个大珠子（大区间）可以由两个较小的珠子(小区间) (与两颗珠子的大小无关，仅需保证能够聚合成大珠子即可，即断点的位置不影响聚合成这颗珠子) 聚合（合并）而来。
所以，我们可以用区间DP来解决本题，方式是枚举断点，从而寻找最优解

状态

状态定义

f[l][r]表示区间左端点为l,右端点为r时释放的最大能量

状态转移

转移条件：无
转移方程：聚合后的区间为[l,r]

设s为断点，新增珠子释放的能量：
[l,s]的头 [s+1,r]的头([l,s]的尾) [s+1,r]的尾([r+1, ]的头) = a[l] a[s + 1] a[r + 1];

再加上两个小区间本来的能量，得状态转移方程：

f[l][r] = \max{f[l][r],f[l][s]+f[s+1][r] + a[l]\times a[s+1]\times a[r+1]};

细节

  1. 题目明确给出，这是一个环，我们要通过把标记数组a 乘二的方式破环为链
  2. 题目中只给了头标记，遇到某一颗或某一串珠子的尾标记是，要将其转为下一颗珠子的头标记
  3. 循环顺序问题：
    若先遍历l再遍历r,可能出现已经转移到了[1,n]但[4,5][n-1,n]等区间尚未计算
    正确方式为:先遍历len(区间长度)再遍历l，从而求出r
  4. 答案不是f[1][n]!! 我们已经破环为链，而在实际的环中，任何一个点都有可能是链的起点,所以答案应为MAX{f[i][i+n-1]}

    代码

    核心代码仅供参考

    re int r;
for(int len = 2;len <= n;len ++){//枚举 区间长度 
    for(int l = 1;l < n * 2 && l + len - 1 <= n * 2;l ++){
        //长度最多为n,右端点不超过2*n 
        r = l + len - 1;
        for(int s = l;s < r;s ++){//枚举断点
            f[l][r] = max(f[l][r],f[l][s]+f[s+1][r] + a[l]*a[s+1]*a[r+1]);
        }
    }
}