P1880 [NOI1995] 石子合并

本题链接：P1880 [NOI1995] 石子合并

本博客给出本题截图：

AC代码

代码解释：区间dp的板子题，对于一个环形的区间思考起来显然是没有一个线性的区间好去思考问题的，这里我们有一种十分常见方便的操作方法，那就是区间开成题目中规定的两倍，然后整体复制，即如下操作：

for (int i = 1; i <= 2 * n; i ++ )
{
	cin >> a[i];
	a[i] = a[i + n];
}

  

 

  
1
  
2
  
3
  
4
  
5
 

我们可以画个图就可以形象的去理解这个是个什么含义，假设我们现在有一个 1 2 3 4 5的环形，现在我们进行如图所示的操作：

这样我们就可以把一个环式结构变成一个线条去处理
本题还需要去一直去进行求和计算，故我们可以使用 前缀和 去进行优化，注意此处需要把长度为2 * n的区间全部进行一次前缀和计算
两个dp数组：f[i][j]的含义为在[i, j]这个区间内进行石子合并的最小值
                      g[i][j]的含义为在[i, j]这个区间内进行石子合并的最大值
这么定义下来就十分的简单明了了，那么如何去写这个状态转移方程呢？在我们把[i ,j]这个区间内的石子进行合并的时候，其实也是把两堆合并成了一堆，所以我们可以根据把这堆石子分成哪两堆进行状态转移，即假设我们是把石子分成了[i, k]和[k + 1, j]这么两堆(i <= k < j)即可

代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int a[N], s[N];
int f[N][N], g[N][N];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++ )
	{
		int w;
		cin >> w;
		a[i] = a[i + n] = w;
	}
	
	for (int i = 1; i <= 2 * n; i ++ ) s[i] = s[i - 1] + a[i];
	
	memset(f, 0x3f, sizeof f);
	memset(g, -0x3f, sizeof g);
	
	for (int len = 1; len <= n; len ++ )
		for (int i = 1; i + len - 1 <= 2 * n; i ++ )
		{
			int j = i + len - 1;
			if (len == 1) f[i][j] = g[i][j] = 0;
			else
			{
				for (int k = i; k < j; k ++ )
				{
					f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
					g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
				}
			}
		}
	
	int maxv = -INF, minv = INF;
	for (int i = 1; i <= n; i ++ )
	{
		maxv = max(maxv, g[i][i + n - 1]);
		minv = min(minv, f[i][i + n - 1]);
	}
	
	cout << minv << endl << maxv << endl;
	
	return 0;
}

  

 

  
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
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/120824499