题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输出样例#1： 复制
43
54
思路：
就是在普通的石子合并的基础上，改成环形的而已。
转移方程依旧是dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j])dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j])。
解决方法就是
将换拆成链，那么拆成连的过程总要将其长度变为2倍，DP依旧按照原来的DP方案，最主要的变化在于
答案的输出的时候。
原来线性合并的答案在dp[1][n]dp[1][n].
因为在不同地方拆开，所以，要在dp[1][n],dp[2][n+1],dp[3][n]...dp[n−1][2∗n−1]dp[1][n],dp[2][n+1],dp[3][n]...dp[n−1][2∗n−1]中寻找最值，即为答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<time.h>
#include<queue>
#include <chrono>
#include <random>
#define ll long long int
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[]={,,,,,,,,,,,,};
int dir[][]={, ,, ,-, ,,-};
int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};
const int inf=0x3f3f3f3f;
const ll mod=1e9+;
int dpmin[][];
int dpmax[][];
int a[];
int sum[];
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
memset(dpmin,inf,sizeof(dpmin));
for(int i=;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
for(int i=;i<=*n;i++){
sum[i]=sum[i-]+a[i];
dpmin[i][i]=;
} for(int len=;len<=n;len++){ //枚举长度
for(int i=;i+len<=*n;i++){ //枚举起始点
int j=i+len-; //结束点
//dpmin[i][j]=inf;
for(int k=i;k<j;k++){ //枚举分割点
dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+][j]-sum[i-]+sum[j]);
dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+][j]-sum[i-]+sum[j]);
}
//cout<<dpmin[i][j]<<endl;
}
}
int ansmin=inf;
int ansmax=-inf;
for(int i=;i<=n;i++){
ansmin=min(ansmin,dpmin[i][i+n-]);
ansmax=max(ansmax,dpmax[i][i+n-]);
}
cout<<ansmin<<endl<<ansmax<<endl;
return ;
}