P1880 [NOI1995] 石子合并 · znzryb
## 思路讲解
注意石子是一个圈，这个时候化曲为直，化为长度为两倍的序列
然后区间dp一般是O(n**3)的，因为序列的合并可能发生在任何地方，不一定是头和尾
## AC代码
AC [https://www.luogu.com.cn/record/197959001](https://www.luogu.com.cn/record/197959001)
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::array<ll,3> arr;
const ll MAXN=217;
ll N,T,A[MAXN],dp_min[MAXN][MAXN],dp_max[MAXN][MAXN],sumA[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
std::cin>>N;
for(int i=1;i<=N;++i){
std::cin>>A[i];
sumA[i]=A[i]+sumA[i-1];
}
for(int i=N+1;i<=2*N;++i){
A[i]=A[i-N];
sumA[i]=A[i]+sumA[i-1];
}
// 初始化dp数组
for(int i=1;i<=2*N;++i){
dp_min[i][i] = 0;
dp_max[i][i] = 0;
}
// 计算最小得分
for(int len=2;len<=N;++len){
for(int i=1;i<=2*N-len+1;++i){
int j = i + len - 1;
dp_min[i][j] = 1e18+7;
dp_max[i][j] = 0;
for(int k=i;k<j;++k){
ll cost = sumA[j] - sumA[i-1];
dp_min[i][j] = std::min(dp_min[i][j], dp_min[i][k] + dp_min[k+1][j] + cost);
dp_max[i][j] = std::max(dp_max[i][j], dp_max[i][k] + dp_max[k+1][j] + cost);
}
}
}
ll min_ans = 1e18+7;
ll max_ans = 0;
for(int i=1;i<=N;++i){
min_ans = std::min(min_ans, dp_min[i][i+N-1]);
max_ans = std::max(max_ans, dp_max[i][i+N-1]);
}
std::cout<<min_ans<<"\n";
std::cout<<max_ans<<"\n";
return 0;
}
/*
AC https://www.luogu.com.cn/record/197959001
*/
```
## 心路历程（WA，TLE，MLE……）
WA
[https://www.luogu.com.cn/record/197954954](https://www.luogu.com.cn/record/197954954)
序列的合并可能发生在任何地方，不一定是头和尾
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::array<ll,3> arr;
const ll MAXN=217;
ll N,T,A[MAXN],dp[MAXN][MAXN],sumA[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
std::cin>>N;
for(int i=1;i<=N;++i){
std::cin>>A[i];
sumA[i]=A[i]+sumA[i-1];
}
for(int i=N+1;i<=2*N;++i){
A[i]=A[i-N];
sumA[i]=A[i]+sumA[i-1];
}
// 注意石子是一个圈，所以我们搞一个长度为2*n的链
// 先最小化得分
for(int i=2*N;i>=1;--i){
for(int j=i+1;j<=2*N;++j){
// 从i到j 区间 最小得分 从i+1到j区间转移过来
dp[i][j]=std::min(dp[i+1][j]+sumA[j]-sumA[i]+A[i],
// 从i到j-1区间转移过来
dp[i][j-1]+sumA[j-1]-sumA[i-1]+A[j]);
}
}
ll ans=1e18+7;
for(int i=1;i<=N;++i){
ans=std::min(dp[i][i+N-1],ans);
}
std::cout<<ans<<"\n";
std::memset(dp, 0, sizeof(dp));
// 先最大化得分
for(int i=2*N;i>=1;--i){
for(int j=i+1;j<=2*N;++j){
// 从i到j 区间 最大得分 从i+1到j区间转移过来
dp[i][j]=std::max(dp[i+1][j]+sumA[j]-sumA[i]+A[i],
// 从i到j-1区间转移过来
dp[i][j-1]+sumA[j-1]-sumA[i-1]+A[j]);
}
}
ans=0;
for(int i=1;i<=N;++i){
ans=std::max(dp[i][i+N-1],ans);
}
std::cout<<ans<<"\n";
return 0;
}
/*
4
4 5 9 4
4616 4 14 12 0 3 11 8 18 2 6 8 6 7 13 7 8 14 11 2 16 12 16 0 8 1 3 10 7 16 0 16 11 17 13 18 5 15 0 12 19 0 0 5 3 1
2087
10554
*/
```