信息学奥赛一本通 1569：【 例 1】石子合并 | 洛谷 P1880 [NOI1995] 石子合并

【题目链接】

ybt 1569：【 例 1】石子合并
洛谷 P1880 [NOI1995] 石子合并

【题目考点】

1. 动态规划：区间动规

2. 环形序列问题

解决方法：破环为链
将长为n的环形序列变为长为$2n-1$的链式序列
原序列：$a_1,a_2,...,a_{n-1},a_n$，$a_n$的下一个元素为$a_1$，形成环形序列。
破坏为链后，得到线性序列
$a_1,a_2,...,a_{n-1},a_n,a_{n+1},a_{n+2},...,a_{2n-1}$
其中$a_{n+1}=a_1$， $a_{n+2}=a_2$, …, $a_{2n-1}=a_{n-1}$
环形序列中的任意区间，都能在线性序列中找到。

例：原序列中$a_{n-1},a_n,a_1,a_2$，在新的序列中就是$a_{n-1},a_n,a_{n+1},a_{n+2}$

【解题思路】

环形摆放n堆石子，合并时第n堆可以和第1堆合并。
面对环形序列问题，首先进行破坏为链，得到长为$2n-1$的线性序列a。
而后求出a序列的前缀和数组s。
在a序列上进行区间动规

1. 状态定义

• 阶段：关注$a_i\sim a_j$，即a序列区间$[i,j]$。
• 决策：将哪两堆石子合并
• 策略：合并石子的方案
• 策略集合：a序列区间$[i,j]$中元素的所有合并方案
• 条件：分数最大或最小
• 统计量：分数

状态定义：
$dpMi{n}_{i,j}$：a序列区间$[i,j]$中元素的所有合并方案中，分数最小的方案的分数。
$dpMa{x}_{i,j}$：a序列区间$[i,j]$中元素的所有合并方案中，分数最大的方案的分数。

由于所有a序列中的元素都是非负整数，那么合并的得分为非负整数。
求$dpMax$时，求最大值，$dpMax$数组所有元素初值为$0$即可。
求$dpMin$时，求最小值，$dpMin$数组初值应该很大，先设为$INF$。

一堆石子无法合并，合并的分数为0，那么设初值$dpMa{x}_{i,i}=dpMi{n}_{i,i}=0$

2. 状态转移方程

策略集合：a序列区间$[i,j]$中元素的所有合并方案
最后一次的决策为最后一步如何合并。
a序列区间$[i,j]$中元素进行合并，最后一步是两堆石子进行合并。接下来需要考虑这两堆石子分别由a序列中哪两个区间中的元素合并得到的。
设区间$[i,j]$的分割点为$k$。a序列区间$[i,k]$中元素合并为第一堆石子，区间$[k+1,j]$中元素合并为第2堆石子。第一个区间长度为1时$k$最小，为$i$。第二个区间长度为1时$k$最大，为$j-1$。所以$i\le k<j$。
已知a序列的前缀和为s，那么a序列区间$[i,j]$中元素加和为$s_j-s_{i-1}$。
对于a序列区间$[i,j]$中元素进行合并能得到的最大分数$dpMa{x}_{i,j}$，先将区间$[i,k]$中元素合并，得到最大分数$dpMa{x}_{i,k}$。再将区间$[k+1,j]$中元素合并，得到最大分数$dpMa{x}_{k+1,j}$，再将两堆石子合并，合并分数为a序列区间$[i,j]$中元素加和$s_j-s_{i-1}$，即$dpMa{x}_{i,j}=dpMa{x}_{i,k}+dpMa{x}_{k+1,j}+s_j-s_{i-1}$。
对于所有可能的$k$的取值，求$dpMa{x}_{i,j}$的最大值。
状态转移方程为：
d p M a x i , j = max ⁡ { d p M a x i , k + d p M a x k + 1 , j + s j − s i − 1 } , i ≤ k < j dpMax_{i,j}=\max\{dpMax_{i,k}+dpMax_{k+1,j}+s_j-s_{i-1}\}, i\le k < j dpMaxi,j​=max{dpMaxi,k​+dpMaxk+1,j​+sj​−si−1​},i≤k<j
同理：
d p M i n i , j = max ⁡ { d p M i n i , k + d p M i n k + 1 , j + s j − s i − 1 } , i ≤ k < j dpMin_{i,j}=\max\{dpMin_{i,k}+dpMin_{k+1,j}+s_j-s_{i-1}\}, i\le k < j dpMini,j​=max{dpMini,k​+dpMink+1,j​+sj​−si−1​},i≤k<j

3. 区间动规的具体实现

区间动规中，长度较小区间的状态是长度较长区间的状态的子状态。因此需要先求出长度较小的区间的状态，再求出长度较长的区间的状态。
外层循环的循环控制变量为区间长度$len$，$len$为1的情况已经求出，因此$len$最小为2，$len$最大时只考虑长为$n$的区间（因为环形序列上中最长的区间长度为n），因此$len$从2循环到n。

内层循环控制变量为区间左端点$i$，在整个长为$2n-1$的a序列上，所有以$i$为起点长为$len$的区间的状态都要求出，区间的右端点为$i+len-1$，最后一个求出的区间的右端点为$2n-1$，因此$i$最小时为1，$i$最大时满足$i+len-1=2n-1$，即$i+len-1<2n$。

在循环控制变量为$i$的循环内部，求出区间右端点$j=i+len-1$。枚举分割点$k$，执行状态转移方程。

求结果时，要把长为$n$的环形序列合并为一堆石子，这个长为$n$的环形序列在长为$2n-1$的$a$序列上对应的区间可以是$[1,n]$, $[2,n+1]$, …, $[n-1,2n-2]$, $[n,2n-1]$。左端点为$i$的长为n的区间，为$[i,i+n-1]$，$1\le i\le n$。
以上所有长为$n$的区间的$dpMax$的最大值，为将$n$堆石子合并的最大得分。
以上所有长为$n$的区间的$dpMin$的最小值，为将$n$堆石子合并的最小得分。

【题解代码】

解法1：区间动规 破环为链

#include<bits/stdc++.h>
using namespace std;
#define N 205
#define INF 0x3f3f3f3f
int a[N], n, s[N];//s：a序列的前缀和 
int dpMin[N][N];//dpMin[i][j]：a[i]...a[j]进行合并的所有方案中，得分最少的方案的得分 
int dpMax[N][N];//dpMax[i][j]：a[i]...a[j]进行合并的所有方案中，得分最高的方案的得分 
int main()
{cin >> n;for(int i = 1; i <= n; ++i){cin >> a[i];a[i+n] = a[i];}for(int i = 1; i < 2*n; ++i)s[i] = s[i-1]+a[i];memset(dpMin, 0x3f, sizeof(dpMin));for(int i = 1; i < 2*n; ++i)dpMin[i][i] = 0;for(int len = 2; len <= n; ++len)for(int i = 1; i+len-1 < 2*n; ++i){int j = i+len-1;for(int k = i; k < j; ++k){dpMin[i][j] = min(dpMin[i][j], dpMin[i][k]+dpMin[k+1][j]+s[j]-s[i-1]);dpMax[i][j] = max(dpMax[i][j], dpMax[i][k]+dpMax[k+1][j]+s[j]-s[i-1]);}}int ansMax = 0, ansMin = INF;for(int i = 1; i <= n; ++i){ansMax = max(ansMax, dpMax[i][i+n-1]);ansMin = min(ansMin, dpMin[i][i+n-1]);}cout << ansMin << endl << ansMax;return 0; 
}