能量项链(P1063 [NOIP 2006 提高组] ) 题解题目概述有nnn个珠子每颗珠子是一个二元组ai,ai1a_i,a_{i1}ai​,ai1​其中aia_iai​被视为头标记ai1a_{i1}ai1​视为尾标记组成一个环。两颗相邻的珠子前一颗的尾标记必定等于后一颗的尾标记如果将这两颗珠子合并那么所释放的能量就是m×r×nm \times r \times nm×r×n这里视m为第一颗珠子的头标记r为第一颗珠子的尾标记、第二颗珠子的头标记n为第二颗珠子的尾标记那么将所有珠子合并为 1 颗珠子的时候能够释放出的最大能量值。题目分析一颗珠子是ai,ai1 a_i,a_{i1}ai​,ai1​的二元组计算两颗珠子聚合的时候只需用计算ai−1×ai×ai1a_{i-1} \times a_i \times a_{i1}ai−1​×ai​×ai1​即可。还有一点就是原题描述中至于珠子的顺序你可以这样确定将项链放到桌面上不要出现交叉随意指定第一颗珠子然后按顺时针方向确定其他珠子的顺序。人话翻译过来就是一个环可以选择任意一个珠子作为起点。思路分析⚡️解法1区间DP这一道题我们先考虑一个小问题合并l∼rl \sim rl∼r的珠子有多少种情况我们可以通过枚举一个断点kkk以此确定最优方案如下1 2 (3 4) - 1 (2 (3 4) ) - (1 (2 (3 4)) - (1 2)(3 4) -((1 2)(3 4))1 (2 3) 4 - (1 (2 3)) 4 -((1 (2 3))4) - .....(1 2) 3 4......通过这样的思想我们可以想到 DP设定dp[l][r]为第lll颗珠子到第rrr颗珠子的最大聚合能量像这样求区间的问题称之为区间 DP。最主要的思想就是枚举区间长度枚举左端点求出右端点枚举分割点如下for(intlen2;lenn;len){//枚举长度for(intl1;llen-1n;l){//枚举左端点intrllen-1;//计算右端点dp[l][r]__;//dp[l][r]初始化for(intkl;kr;k){//动态转移方程式}}}示意图于是我们就可以很愉快的得到动态转移方程dp[l][r]max(dp[l][r],dp[l][k]dp[k1][r]a[l]*a[k1]*a[r1]);代码也很快能够得出只不过需要破环成链同时l循环也要改成for(int l1;llen-12*n-1;l)。AC code#includebits/stdc.husingnamespacestd;intn;inta[201];longlongdp[201][201];intmain(){cinn;for(inti1;in;i){cina[i];a[in]a[i];}for(intlen2;lenn;len){for(intl1;llen-12*n-1;l){intrllen-1;for(intkl;kr;k){dp[l][r]max(dp[l][r],dp[l][k]dp[k1][r]a[l]*a[k1]*a[r1]);}}}longlongmaxx0;for(inti1;in;i){maxxmax(maxx,dp[i][in-1]);}coutmaxx;}疑难杂症问为什么是a[l]*a[k1]*a[r1]答我们这里枚举的是最后一次合并的分割点所以头标记是ala_lal​尾标记就是ara_rar​。问为什么枚举分割点只枚举到r-1答因为那样就会回到原问题l∼rl \sim rl∼r。尾声本题是一道值得练手的区间DP题思路大差不差只不过多了环形需要破环成链。