【題目鏈接】

ybt 1570：【例 2】能量項鏈
ybt 1843：【06NOIP提高組】能量項鏈
洛谷 P1063 [NOIP 2006 提高組] 能量項鏈

【題目考點】

1. 動態規劃：區間動規

2. 環形序列

解決方法：破環為鏈
模板題：洛谷 P1880 [NOI1995] 石子合并

【解題思路】

本題與洛谷 P1880 [NOI1995] 石子合并十分類似，可以先做上題，而后做本題。
環形序列上的問題，首先進行破環為鏈，將長為n的輸入a序列變為長為$2n$的a序列。其中$a_{i+n}=a_i,1\le i\le n$。
原環形序列為由n個珠子構成的環形序列。破環為鏈后得到的是由$2n?1$個珠子構成的線性序列。該線性序列為一個假想的$b$序列，$b$序列的每個元素為一個珠子，第i顆珠子$d_i$的頭標記為$a_i$，尾標記為$a_{i+1}$。最后第$2n?1$個珠子$b_{2n?1}$的頭標記為$a_{2n?1}$，尾標記為$a_{2n}$。

1. 狀態定義

• 階段：第i個珠子到第j個珠子，即b序列區間$[i,j]$
• 決策：合并哪兩個珠子
• 策略：合并的方案
• 策略集合：b序列區間$[i,j]$的所有合并方案
• 條件：獲得能量最大
• 統計量：能量

狀態定義：$d{p}_{i,j}$：b序列區間$[i,j]$的所有合并方案中，獲得能量最大的方案所獲得的能量。
初始狀態：1顆珠子無法合并，獲得能量為0。因此$d{p}_{i,i}=0$

2. 狀態轉移方程

• 策略集合：b序列區間$[i,j]$的所有合并方案
  根據最后一次將哪兩個珠子合并，來分割策略集合。

設存在分割點$k$，將區間$[i,j]$分割為區間$[i,k]$與區間$[k+1,j]$。自然$i\le k<j$。
要想求$d{p}_{i,j}$：

• 先將b序列區間$[i,k]$合并為一個珠子，獲得能量$d{p}_{i,k}$。得到珠子的頭標記為$b_i$的頭標記$a_i$，尾標記為$b_k$的尾標記$a_{k+1}$。
• 再將b序列區間$[k+1,j]$合并為一個珠子，獲得能量$d{p}_{k+1,j}$。得到珠子的頭標記為$b_{k+1}$的頭標記$a_{k+1}$，尾標記為$b_j$的尾標記$a_{j+1}$。
• 而后再將這兩個珠子合并，獲得能量$a_i?a_{k+1}?a_{j+1}$。

求出$d{p}_{i,j}=d{p}_{i,k}+d{p}_{k+1,j}+a_i?a_{k+1}?a_{j+1}$
枚舉分割點$k$的所有可能情況，求出每種情況下狀態的最大值。
狀態轉移方程為：
d p i , j = max ? { d p i , k + d p k + 1 , j + a i ? a k + 1 ? a j + 1 } , i ≤ k < j dp_{i,j} = \max\{dp_{i,k}+dp_{k+1,j}+a_i\cdot a_{k+1}\cdot a_{j+1}\}, i\le k < j dpi,j?=max{dpi,k?+dpk+1,j?+ai??ak+1??aj+1?},i≤k<j

3. 具體實現

由于求滿足條件的最大值，dp數組初值應該為很小的值。由于所有可能的狀態值都是非負整數，因此dp數組初值可以為0。
對于長為1的區間的狀態，1個珠子無法合并獲得能量，因此$d{p}_{i,i}=0$
外層循環為區間長度len，len最小為2，最大為n。
內層循環為區間左端點i，i最小為1。由于破環為鏈后$b$序列共有$2n?1$個元素，i最大時，區間右端點$i+len?1$為$2n?1$，因此$i+len?1<2n$
取區間右端點$j=i+len?1$，在$i\le k<j$范圍內枚舉分割點$k$，執行狀態轉移方程。
最后，枚舉$b$序列上所有長為$n$的區間，包括$[1,n],[2,n+1],...,[n?1,2n?2],[n,2n?1]$，即$[i,i+n?1],1\le i\le n$。求出每個區間的狀態值$d{p}_{i,i+n?1}$的最大值，即為合并環形序列上珠子能獲得的最大能量。

【題解代碼】

解法1：區間動規 破環為鏈

#include<bits/stdc++.h>
using namespace std;
#define N 205
int a[N], n, ans, dp[N][N];//dp[i][j]：第i珠子到第j珠子有聚合方案中，釋放的能量最大的方案的能量   
int main()
{cin >> n;for(int i = 1; i <= n; ++i){cin >> a[i];a[i+n] = a[i];}for(int len = 2; len <= n; ++len)//由于都是正整數，求最大值。dp初值為很小的值，可以為0。dp[i][i] = 0 {for(int i = 1; i+len-1 < 2*n; ++i){int j = i+len-1;for(int k = i; k < j; ++k)dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]); }}for(int i = 1; i <= n; ++i)ans = max(ans, dp[i][i+n-1]);cout << ans;return 0;
}
``