洛谷p1880石子合并

题目链接：https://www.luogu.com.cn/problem/P1880

正宗的石子合并，当然，这个题不同于弱化版的是他是环形石子合并，因为题目说在一个圆形操场的四周摆放

大体思路：

大体思路同石子合并弱化版一致，但是初始化时候要扩充两倍。

具体操作参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[300];
 4 int dp[300][300];//从i到j所付出的最小价值 
 5 int up[300][300];//从i到j所付出的最大价值 
 6 int sum[300];//从区间i到区间j的石子堆和 
 7 int n;
 8 void minval()
 9 {
10     for(int len=1;len<2*n;len++)//区间长度，i--j的长度，但是要扩充到2*n 
11     {
12         for(int i=1;i<=2*n-len;i++)//起点i同样要扩充 
13         {
14             int j=i+len;//终点 
15             dp[i][j]=INT_MAX;//最小标兵初始化最大 
16             up[i][j]=-1;//最大标兵初始化最小 
17             for(int k=i;k<j;k++)//区间i-k-j
18             {
19                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);//详情请看上一篇博文 
20                 up[i][j]=max(up[i][j],up[i][k]+up[k+1][j]+sum[j]-sum[i-1]);//详情请看上一篇博文 
21             }
22         }
23     }
24 }
25 int main()
26 {
27     int ans=INT_MAX,cnt=0;
28     ios::sync_with_stdio(false);
29     cin>>n;
30     for(int i=1;i<=n;i++)
31     cin>>a[i];
32     for(int i=1;i<=2*n;i++)//扩充2倍 
33     {
34         a[i+n]=a[i];//环形赋值 
35         sum[i]=sum[i-1]+a[i];
36         dp[i][i]=0;
37         up[i][i]=0;
38     }
39     minval();
40     for(int i=1;i<=n;i++)
41     {
42         ans=min(ans,dp[i][i+n-1]);//区间内最小的 
43         cnt=max(cnt,up[i][i+n-1]);//区间内最大的 
44     }
45     cout<<ans<<endl<<cnt;
46     return 0;
47 }

洛谷p1880石子合并

推荐阅读