P1880 [NOI1995]石子合并

题目描述

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入格式

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式

输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例

输入 #1

4

4 5 9 4

输出 #1

43

54

【思路】

区间DP

【核心思路】

又是围成一个圈

所以处理方式很显然

就是在原来的序列后面放一个和原来序列一样的序列就可以了

这样2-n+1区间就是存在的

而且是那1-n个数

就是起点不同而已

每次合并后的值等于原来合并的价值

加上

这次合并的石子数

如果只用一个二维数组f[i][j]的话显然是没有办法保存的

所以可以利用一个很优美的东西

前缀和

利用前缀和可以求出某个区间的石子数

也就是可以知道每次石子合并可以新得到的值

那么就可以只用f[i][j]来存i-j区间内

合并石子的最值就好了

【DP式】

DP方程式：

f1[i][j] = max(f1[i][j],f1[i][k] + f1[k + 1][j] + cost[i][j])

f2[i][j] = min(f2[i][j],f2[i][k] + f2[k + 1][j] + cost[i][j])

（一个求区间最大值，一个求区间最小值）

这个区间的最值就等于分成两个小区间合并起来之后的最值

【最终结果】

最后结果

自然是比较i-i + n - 1这个区间啦

因为圈不同于一条线的就是可以任选起点

所以要比较以每一个作为起点时的最值

输出就好了

【完整代码】

#include<iostream>

#include<cstdio>

using namespace std;

const int Max = 206;

int f1[Max][Max];

int f2[Max][Max];

int a[Max];

int sum[Max];

int cost[Max][Max];

int main()

{

	int n;

	cin >> n;

	for(register int i = 1;i <= n;++ i)

		cin >> a[i],a[i + n] = a[i];

	for(register int i = 1;i <= n * 2;++ i)

		sum[i] = sum[i - 1] + a[i];

	for(register int i = 1;i <= n * 2;++ i)

		for(register int j = i;j <= n * 2;++ j)

			cost[i][j] = sum[j] - sum[i - 1];

	for(register int len = 1;len <= n;++ len)

	{

		for(register int i = 1;i + len - 1 <= n * 2;++ i)

		{

			int j = i + len - 1;

			if(i != j)

			f2[i][j] = 999999999;

			for(register int k = i;k < j;++ k)

				f1[i][j] = max(f1[i][j],f1[i][k] + f1[k + 1][j] + cost[i][j]),

				f2[i][j] = min(f2[i][j],f2[i][k] + f2[k + 1][j] + cost[i][j]);

		}

	}

	int M = 0;

	int MM = 0x7fffffff;

	for(register int i = 1;i <= n;++ i)

		M = max(M,f1[i][i + n - 1]),

		MM = min(MM,f2[i][i + n - 1]);

	cout << MM << endl << M << endl;

	return 0;

}

巴特西

洛谷 P1880 [NOI1995]石子合并题解

P1880 [NOI1995]石子合并

题目描述

输入格式

输出格式

输入输出样例

【思路】

【核心思路】

【DP式】

【最终结果】

【完整代码】

最新文章

热门文章

巴特西

洛谷 P1880 [NOI1995]石子合并 题解

P1880 [NOI1995]石子合并

题目描述

输入格式

输出格式

输入输出样例

【思路】

【核心思路】

【DP式】

【最终结果】

【完整代码】

最新文章

热门文章

洛谷 P1880 [NOI1995]石子合并题解