石子合并（动态规划）

传送门
分析：首先起始位置未知，不能随意根据最大或最小作为起始点，因为例如想求最大的，原理就是先找最大的，因为每个求和都把前面的和加一遍，所以此时前面的和最大才能求出后面的最大解，所以必须用for循环动态规划！
接着要求是环状的，所以一定有首位相加的情况，此时就开一个2倍的数组，这样首尾就可以一起讨论了。
3.求其递推方程
其递推方程：m[i][j] = m[i][k]+m[k+1][j] + sum [j] - sum [i -1];
4.递推方程的解释：
前面的m[i][k] 和 m[k+1][j] ：i到k合并成一堆，k+1到j又合并成一堆
后面的sum[j] - sum[i -1]: 这里表示的是刚形成的两堆 再合并到一块的石子数
也就是用前缀和来求区间和
比如有（1，2，3，4，5，6）这里表示的是有6堆石子
现在我们求m[3][6] = m[3][4]+m[5][6] + sum[6] - sum[2]

							  sum[6]:表示的是将这6堆全部合并在一起 
							  sum[2]:表示的是将前两堆合并在一起
							  
							  现在我们要求后4堆的和 那不就是sum[6] - sum [2]; 		 **
1
2
3
4

ac代码：

#include<stdio.h>
#include<algorithm>
using  namespace std;
int a[410],sum[410],dp[410][410],dd[410][410];
int inf=0x3f3f3f3f;
int main()
{
	int n,i,j,t,ans1,ans2;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i+n]=a[i];
		dp[i][i]=dd[i][i]=0;
	}
	for(i=1;i<=2*n;i++)
	sum[i]=a[i]+sum[i-1];//求出前缀和，方便后边区间相加 
	for(i=2;i<=n;i++)
//区间长度，因为要从最小的区间开始求最小最大化，所以区间要从2开始控制 如果从1的话  循环完dp[1] dd[1]=inf,影响整体了 
	for(j=1;j<=2*n-(i-1);j++)//起点位置，区间长度变化，起点也随着变化，防止越界 
	{
		int k=j+i-1;//末位置  
		dd[j][k]=-inf;
		dp[j][k]=inf;
		for(t=j;t<k;t++)
//从小区间开始，这样求出来才能推大区间 小区间不断变化 所以找一个中介点
		{
		dd[j][k]=max(dd[j][k],dd[j][t]+dd[t+1][k]+sum[k]-sum[j-1]);
		dp[j][k]=min(dp[j][k],dp[j][t]+dp[t+1][k]+sum[k]-sum[j-1]);
		}
	}
	ans1=-inf;
	ans2=inf;
	for(i=1;i<=n;i++)//i为起点，遍历出长度为n的环 
    {
		ans1=max(dd[i][i+n-1],ans1);
		ans2=min(dp[i][i+n-1],ans2);
	}
	printf("%d\n%d\n",ans2,ans1);	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40